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