| 比赛 |
2026.3.28 |
评测结果 |
WTTTTTTTTTT |
| 题目名称 |
Good Cyclic Shifts |
最终得分 |
0 |
| 用户昵称 |
张雨晴 |
运行时间 |
21.009 s |
| 代码语言 |
C++ |
内存使用 |
5.68 MiB |
| 提交时间 |
2026-03-28 11:26:45 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int t;
const int M=500005;
int p[M];
int ans[M];
int c[M];
int n;
bool check(int l,int r,int mv){
int lim=0;
for(int i=l;i<=r;i++){
c[p[i]]=i;
lim+=(abs(p[i]-i))/2;
}
// for(int i=1;i<=n;i++){
// cout<<c[i]<<" ";
// }
// cout<<"\n";
for(int i=l;i<=r;i++){
// cout<<"i"<<" "<<i<<"\n";
if(c[i-n+mv]<i){//往右走
int step=c[i-n+mv];
while(step!=i){
c[p[step]]++;
c[p[step+1]]--;
// cout<<"swap"<<p[step]<<" "<<p[step+1]<<"\n";
swap(p[step],p[step+1]);
step++;
lim--;
}
}else if(c[i-n+mv]>i){//往左走
int step=c[i-n+mv];
// cout<<step<<"\n";
while(step!=i){
c[p[step]]--;
c[p[step-1]]++;
// cout<<"swap"<<p[step]<<" "<<p[step-1]<<"\n";
swap(p[step],p[step-1]);
step--;
lim--;
}
}else{
continue;
}
}
if(lim<0) return false;
else return true;
}
int main(){
freopen("Shifts.in","r",stdin);
freopen("Shifts.out","w",stdout);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
p[i+n]=p[i];
}
memset(ans,0,sizeof(ans));
int cnt=0;
for(int i=0;i<n;i++){
int l=n+1-i;
int r=n+n-i;
// cout<<l<<" "<<r<<"\n";
// for(int j=l;j<=r;j++) cout<<p[j]<<" ";
// cout<<"\n";
if(check(l,r,i)){
ans[++cnt]=i;
}
}
cout<<cnt<<"\n";
for(int i=1;i<=cnt;i++) cout<<ans[i]<<" ";
cout<<"\n";
}
return 0;
}