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