ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214247 | #2022. a | x_add_b | 60 | 3ms | 1324kb | C++ | 1.7kb | 2024-11-16 20:14:28 | 2024-11-16 23:12:10 |
answer
#include<bits/stdc++.h>
namespace IO
{
template<typename Type>
void read(Type &x){
char ch=getchar();
x=0;bool f=0;
while(ch<'0'||ch>'9')
f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')
x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();
x=f?-x:x;
}
}
using namespace std;
#define N 32005
#define M 4000005
int n,maxval,pos,idx,tot,L,R,ans;
int a[N],cnt[N],seq[N];
struct sol
{
int l,r;
}s1[M*15];
void solve(int l,int r,int val)
{
pos=0;
for(int i=l;i<=r;i++)
if(a[i]==val) seq[++pos]=i;
if(pos==1) R=seq[1];
if(pos>1){
tot=seq[pos/2];
L=tot-1;
for(int i=pos/2-1;i>=1;i--){
for(int j=seq[i];j<L;j++){
s1[++idx]={j,j+1};
swap(a[j],a[j+1]);
}
L--;
}L++;
R=tot+1;
for(int i=pos/2+1;i<=pos;i++){
for(int j=seq[i];j>R;j--){
s1[++idx]={j-1,j};
swap(a[j-1],a[j]);
}
R++;
}R--;
}
if(l<R) s1[++idx]={l,R};
for(int i=l,j=R;i<j;i++,j--)
swap(a[i],a[j]);
// printf("%d\n",val);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// puts("");
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
IO::read(n);
for(int i=1;i<=n;i++)
IO::read(a[i]),maxval=max(maxval,a[i]),cnt[a[i]]++;
for(int i=1;i<=maxval;i++)
cnt[i]+=cnt[i-1];
for(int i=0;i<maxval;i++){
if(cnt[i]==cnt[i-1]) continue ;
// printf("%d %d %d\n",cnt[i-1]+1,n,i);
solve(cnt[i-1]+1,n,i);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// printf("\n%d\n",idx);
}
printf("%d\n",idx);
// for(int i=1;i<=idx;i++)
// ans+=(s1[i].r-s1[i].l+1);
// printf("%d\n",ans);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// puts("");
for(int i=1;i<=idx;i++)
printf("%d %d\n",s1[i].l,s1[i].r);
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1284kb
input:
63 19732 30594 10113 7702 9784 6421 4697 13517 5317 8508 26509 15653 2986 31587 11246 12158 24378 49...
output:
59 1 43 2 31 3 37 4 33 5 32 6 50 7 55 8 18 9 22 10 44 11 42 12 61 13 45 14 31 15 57 16 45 17 27 18 5...
result:
ok ok,using 1062 times
Test #2:
score: 0
Accepted
time: 1ms
memory: 1276kb
input:
25 21264 13876 11861 12802 18452 3136 17660 21163 14140 20632 25998 22051 10612 12680 7873 23249 274...
output:
21 1 25 2 20 3 19 4 11 5 13 6 23 7 23 8 23 9 24 11 20 12 22 13 16 14 24 15 16 16 22 17 25 18 22 19 2...
result:
ok ok,using 216 times
Test #3:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
95 26373 31391 7777 12225 25301 24166 2461 4926 15751 18727 29175 18511 17455 16025 16845 6723 3477 ...
output:
89 1 92 2 21 3 17 4 21 5 45 6 11 7 86 8 47 9 38 10 64 11 95 12 81 13 68 14 19 15 67 16 56 17 64 18 9...
result:
ok ok,using 2489 times
Test #4:
score: 0
Accepted
time: 0ms
memory: 1284kb
input:
100 15104 1621 22502 12704 13109 9592 1390 22280 23468 26863 23084 10981 20492 7842 12883 16636 2565...
output:
107 1 70 2 51 3 20 4 31 5 64 6 53 7 9 8 69 9 13 10 85 11 76 12 64 13 22 14 66 15 51 16 99 17 20 18 3...
result:
ok ok,using 2519 times
Test #5:
score: 0
Accepted
time: 0ms
memory: 1284kb
input:
100 13822 19801 16537 25492 24250 30303 18588 13044 8538 23642 864 10878 16671 5509 13062 15457 2577...
output:
97 1 78 2 68 3 15 4 17 5 47 6 98 7 97 8 90 9 79 10 55 11 50 12 54 13 72 14 52 15 61 16 64 17 21 18 7...
result:
ok ok,using 2718 times
Subtask #2:
score: 40
Accepted
Test #6:
score: 40
Accepted
time: 0ms
memory: 1288kb
input:
197 10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...
output:
205 1 140 2 37 3 62 4 119 5 170 6 141 7 144 8 127 9 69 10 125 11 135 12 165 13 138 14 195 15 38 16 6...
result:
ok ok,using 10223 times
Test #7:
score: 0
Accepted
time: 1ms
memory: 1284kb
input:
354 28133 31628 5619 8961 1003 9779 27591 14336 31618 17755 6349 17570 25604 24107 23136 21537 16494...
output:
347 1 42 2 19 3 321 4 236 5 204 6 117 7 322 8 16 9 138 10 45 11 104 12 348 13 40 14 278 15 320 16 10...
result:
ok ok,using 31756 times
Test #8:
score: 0
Accepted
time: 0ms
memory: 1296kb
input:
512 14563 17808 18597 4341 12143 30490 13558 4331 30512 15302 14593 3642 21783 21775 23315 5766 1661...
output:
1248 1 489 2 283 3 128 4 448 5 274 6 222 7 171 8 397 9 276 10 170 11 405 12 505 13 221 14 411 15 253...
result:
ok ok,using 65574 times
Test #9:
score: 0
Accepted
time: 1ms
memory: 1324kb
input:
1000 1502 12015 26522 985 16804 3210 22284 28860 17265 9237 23503 15006 9625 30582 12808 25544 5298 ...
output:
4690 1 78 2 914 3 527 4 238 5 378 6 512 7 553 8 662 9 55 10 777 11 20 12 475 13 618 14 227 15 585 22...
result:
ok ok,using 255164 times
Test #10:
score: 0
Accepted
time: 0ms
memory: 1308kb
input:
1000 220 30195 7500 27597 28712 10097 25659 20392 16159 6016 31747 14902 5036 29017 31162 24365 2359...
output:
2632 1 816 2 941 3 176 4 441 5 893 6 372 7 185 8 881 9 384 10 852 11 655 12 732 13 244 14 26 15 625 ...
result:
ok ok,using 251440 times
Subtask #3:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
input:
29160 3 3 5 5 4 4 5 1 3 2 5 1 4 3 2 3 1 2 1 5 4 4 4 0 2 3 4 2 1 4 4 5 3 3 5 4 2 4 4 1 3 5 1 1 2 2 2 ...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #16:
score: 0
Time Limit Exceeded
input:
25162 6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...
output:
32766550 1 10772 2 20392 3 6712 4 6589 5 496 6 8025 7 19152 23652 23653 23651 23652 23650 23651 2364...