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