| 比赛 |
2026.3.28 |
评测结果 |
AAATATTTTTE |
| 题目名称 |
Good Cyclic Shifts |
最终得分 |
36 |
| 用户昵称 |
小福鑫 |
运行时间 |
16.866 s |
| 代码语言 |
C++ |
内存使用 |
3.75 MiB |
| 提交时间 |
2026-03-28 10:52:12 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int T,n,a[100001],b[100001],f,ans,cnt,r1[100001],q[100001];
void msort1(int s,int e){
if(s==e){
return;
}
int mid=(s+e)/2;
msort1(s,mid);
msort1(mid+1,e);
int i=s,j=mid+1,k=s;
while(i<=mid&&j<=e){
if(b[i]<=b[j]){
r1[k]=b[i];
k++;
i++;
}
else{
r1[k]=b[j];
k++;
j++;
ans+=mid-i+1;
}
}
while(i<=mid){
r1[k]=b[i];
k++;
i++;
}
while(j<=e){
r1[k]=b[j];
k++;
j++;
}
for(int i=s;i<=e;i++){
b[i]=r1[i];
}
return;
}
int main(){
freopen("Shifts.in","r",stdin);
freopen("Shifts.out","w",stdout);
cin>>T;
while(T--){
cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
for(int i=n+1;i<=2*n;i++){
a[i]=a[i-n];
b[i]=a[i];
}
for(int i=2;i<=n+1;i++){
ans=f=0;
for(int j=i;j<=i+n-1;j++){
// cout<<a[j]<<" ";
f+=abs(a[j]-(j-i+1));
b[j]=a[j];
}
// cout<<"\n";
f/=2;
msort1(i,i+n-1);
// cout<<ans<<" "<<f<<endl;
if(ans<=f){
q[++cnt]=n-i+1;
}
}
cout<<cnt<<endl;
for(int i=cnt;i>=1;i--){
cout<<q[i]<<" ";
}
cout<<"\n";
}
}