比赛 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;
}