ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214241 | #2022. a | x_add_b | 0 | 220ms | 32772kb | C++11 | 1.4kb | 2024-11-16 19:30:19 | 2024-11-16 23:11:36 |
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;
int a[N],cnt[N],seq[N];
struct sol
{
int l,r;
}s1[M];
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;i<R-i+1;i++)
swap(a[i],a[R-i+1]);
// printf("%d\n",val);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// puts("");
}
int main()
{
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=1;i<maxval;i++){
if(cnt[i]==cnt[i-1]) continue ;
solve(cnt[i-1]+1,n,i);
}
printf("%d\n",idx);
for(int i=1;i<=idx;i++)
printf("%d %d\n",s1[i].l,s1[i].r);
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
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:
47 1 43 2 31 3 37 4 32 5 32 6 50 7 55 8 16 9 20 10 43 11 27 12 61 13 61 14 45 15 45 18 44 19 46 20 5...
result:
wrong answer sequence hasn't been sorted
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 1284kb
input:
197 10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...
output:
172 1 140 2 37 3 62 4 119 5 170 6 140 7 143 8 125 9 64 10 169 11 37 12 164 13 16 14 195 15 25 16 42 ...
result:
wrong answer sequence hasn't been sorted
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
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 220ms
memory: 32772kb
input:
25162 6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...
output:
53325 1 10772 2 20392 3 6711 4 6587 5 493 6 8024 7 19151 23652 23653 23651 23652 23650 23651 23649 2...
result:
wrong answer too many times