| 比赛 |
2026.3.28 |
评测结果 |
AAAAAAAAAAA |
| 题目名称 |
Good Cyclic Shifts |
最终得分 |
100 |
| 用户昵称 |
梦那边的美好ME |
运行时间 |
1.840 s |
| 代码语言 |
C++ |
内存使用 |
10.61 MiB |
| 提交时间 |
2026-03-28 12:57:15 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T;
ll n;
ll a[410000],l[410000],r[410000],d[410000];
void make(ll aa,ll bb){
if (aa>bb) return;
ll x=(aa%n+n-1)%n+1,y=(bb%n+n-1)%n+1;
if (x<=y){
d[x]++;d[y+1]--;
}else{
d[x]++;d[n+1]--;
d[1]++;d[y+1]--;
}
}
void solve(){
cin>>n;
for (int i=0;i<=2*n;i++){
a[i]=0;l[i]=-1;r[i]=-1;d[i]=0;
}
for (int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
stack <int> q;
for (int i=1;i<=2*n;i++){
while (!q.empty()&&a[q.top()]<=a[i])q.pop();
if (!q.empty()&&i-q.top()<n)l[i]=q.top();
q.push(i);
}
while (!q.empty())q.pop();
for (int i=2*n;i>=1;i--){
while (!q.empty()&&a[q.top()]>=a[i])q.pop();
if (!q.empty()&&q.top()-i<n)r[i]=q.top();
q.push(i);
}
for (int i=1;i<=2*n;++i){
if(l[i]!=-1&&r[i]!=-1){
make(r[i]-n+1,l[i]);
}
}
vector<int> v;
ll res=0;
for (int i=1;i<=n;++i){
res+=d[i];
if (!res) v.push_back((n-i+1)%n);
}
sort(v.begin(),v.end());
cout<<v.size()<<"\n";
for(int i=0;i<v.size();++i){
cout<<v[i]<<" ";
}
cout<<"\n";
}
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--) solve();
return 0;
}