比赛 2026.3.28 评测结果 AAAAATTTTTT
题目名称 Good Cyclic Shifts 最终得分 45
用户昵称 ychyyx 运行时间 16.201 s
代码语言 C++ 内存使用 4.04 MiB
提交时间 2026-03-28 11:30:13
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int T;
int n;
int a[2000005],p[1000005];
int f;
int ans;
int c[1000005];
int tot[100005];
int lowbit(int i){
    return i&(-i);
}
void change(int i,int k){
    for(;i<=n;i+=lowbit(i)){
        c[i]+=k;
    }
}
int sum(int i){
    int s=0;
    for(;i>=1;i-=lowbit(i)){
        s+=c[i];
    }
    return s;
} 
bool check(){
    f=0;
    for(int i=1;i<=n;i++)   f+=abs(p[i]-i);
    f=f*1.0/2; 
    for(int i=1;i<=n;i++){
        change(p[i],1);
    }
    ans=0;
    for(int i=1;i<=n;i++){
        ans+=sum(p[i]-1);
        change(p[i],-1);
    }
    return ans<=f;
}
void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    int k=0;
    for(int s=0;s<n;s++){
        for(int i=1;i<=n;i++){
            p[i]=a[i+n-s];
        }
        if(check()){
            tot[++k]=s;
        }
    }
    printf("%d\n",k);
    for(int i=1;i<=k;i++)
        printf("%d ",tot[i]);
    printf("\n");
}
int main(){
    freopen("Shifts.in","r",stdin);
    freopen("Shifts.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        work(); 
    }
    return 0;
}