比赛 2026.3.28 评测结果 AAAAATTTTTT
题目名称 Good Cyclic Shifts 最终得分 45
用户昵称 exil 运行时间 15.090 s
代码语言 C++ 内存使用 3.99 MiB
提交时间 2026-03-28 09:40:24
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x){
    return x & -x;
}
int shu[1000005];
int n;
void add(int x){
    int cnt=x;
    while(cnt<=n){
        shu[cnt]++;
        cnt+=lowbit(cnt);
    }
}
int cha(int x){
    int cnt=x;
    int c=0;
    while(cnt>=1){
        c+=shu[cnt];
        cnt-=lowbit(cnt);
    }
    return c;
}


signed main(){
    freopen("Shifts.in","r",stdin);
    freopen("Shifts.out","w",stdout);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        vector<int> v;
        vector<int> ans;
        for(int i = 1;i<=n;i++){
            int a;
            cin>>a;
            v.push_back(a);
        }
        for(int i = 1;i<=n;i++){
            int f=0,ansl=0;
            
            for(int j = 1;j<=n;j++)shu[j]=0;
            for(int j = 1;j<=n;j++){
                f+=abs(v[j-1]-j);
                ansl+=j-cha(v[j-1])-1;
                add(v[j-1]);
            }
            //cout<<f/2<<" "<<ansl<<endl;
            if(f/2>=ansl)ans.push_back(i-1);
            
            
            int t=v[n-1];
            v.erase(v.begin()+n-1);
            v.insert(v.begin(),t);
        }
        int len=ans.size();
        cout<<len<<endl;
        for(int i = 0;i<len;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}