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