比赛 2026.3.28 评测结果 AAEWEEEEEEE
题目名称 Good Cyclic Shifts 最终得分 18
用户昵称 彭欣越 运行时间 2.280 s
代码语言 C++ 内存使用 3.46 MiB
提交时间 2026-03-28 12:06:19
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010;
int T,n,a[N],a1[N],c[N],ans,sum;
vector<int>v;
void msort (int l,int r) {
    if (l==r) return;
    ll mid=(l+r)/2;
    msort(l,mid);
	msort(mid+1,r);
	ll ll=l,rr=mid+1,sum=l;
    while (ll<=mid&&rr<=r) {
    	if (a1[ll]<=a1[rr]) c[sum++]=a1[ll++];
    	else c[sum++]=a1[rr++],ans+=mid-ll+1;
	}
    while (ll<=mid) c[sum++]=a1[ll++];
    while (rr<=r) c[sum++]=a1[rr++];
    for (int i=l;i<=r;i++) a1[i]=c[i];
} 
int main () {
    freopen("Shifts.in","r",stdin);
    freopen("Shifts.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> T;
    while (T--) {
        v.clear();
        cin >> n;
        for (int i=1;i<=n;i++) {
            cin >> a[i]; 
            a[i+n]=a[i];
            a1[i]=a[i];
            a1[i+n]=a[i];
        }
        for (int i=n;i>0;i--) {
            sum=ans=0;
            for (int j=1;j<=n;j++) sum+=abs(j-a[j+i]);
            memset(c,0,sizeof(c));
            for (int j=i+1;j<=i+n;j++) a1[j]=a[j];
            msort(i+1,i+n);
            if (sum/2>=ans) v.push_back(n-i); 
        }
        cout << v.size() <<endl;
        for (int i=0;i<v.size();i++) cout << v[i] <<' ';
        cout <<endl;
    }
    return 0;
}