题意分析
发现， $c_i$ 的限制比较多，因此针对此进行 DP。
设 $\textit{dp}{i,j},j\in\set{1,2,3,4}$ 表示食物 $i$ 的状态为 $j$ 的合法状态是从 $\textit{dp}{i-1,\textit{dp}{i,j}}$ 转移得来。同时，规定 $\textit{dp}{i,j}$ 有值表示合法，没有值表示不合法。
那么，有：
\[\begin{aligned} \textit{dp}_{i,1}&= \begin{cases} 3&\textit{dp}_{i-1,3}\land c_{i-1}\geq c_i\\ 4&\textit{dp}_{i-1,4}\land c_{i-1}\geq2c_i\\ \end{cases}\\ \textit{dp}_{i,2}&= \begin{cases} 1&\textit{dp}_{i-1,1}\land c_i\geq c_{i-1}\\ 2&\textit{dp}_{i-1,2}\land2c_i\geq c_{i-1}\\ \end{cases}\\ \textit{dp}_{i,3}&= \begin{cases} 3&\textit{dp}_{i-1,3}\land2c_{i-1}\geq c_i\\ 4&\textit{dp}_{i-1,4}\land c_{i-1}\geq c_i\\ \end{cases}\\ \textit{dp}_{i,4}&= \begin{cases} 1&\textit{dp}_{i-1,1}\land c_i\geq2c_{i-1}\\ 2&\textit{dp}_{i-1,2}\land c_i\geq c_{i-1}\\ \end{cases} \end{aligned}\]但是，发现边界情况不好搞。因为这是一个“环形 DP”，即 $\textit{dp}{n,j}$ 会影响 $\textit{dp}{1,j}$。
对于诸如此类问题，其实直接枚举边界即可。即枚举 $\textit{dp}{1,1}\sim \textit{dp}{1,4}$，之后从 $\textit{dp}{n,j}$ 递推 $\textit{dp}{1,j}$，判断 $\textit{dp}_{1,j}$ 是否有值即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e6;
int n,c[N+1];
int dp[N+1][4];
void move(int a,int b){
if(dp[a][2]!=-1&&c[a]>=c[b]){
dp[b][0]=2;
}else if(dp[a][3]!=-1&&c[a]>=2ll*c[b]){
dp[b][0]=3;
}
if(dp[a][0]!=-1&&c[b]>=c[a]){
dp[b][1]=0;
}else if(dp[a][1]!=-1&&2ll*c[b]>=c[a]){
dp[b][1]=1;
}
if(dp[a][2]!=-1&&2ll*c[a]>=c[b]){
dp[b][2]=2;
}else if(dp[a][3]!=-1&&c[a]>=c[b]){
dp[b][2]=3;
}
if(dp[a][0]!=-1&&c[b]>=2ll*c[a]){
dp[b][3]=0;
}else if(dp[a][1]!=-1&&c[b]>=c[a]){
dp[b][3]=1;
}
}
bool solve(int x){
memset(dp,-1,sizeof(dp));
dp[1][x]=4;
for(int i=2;i<=n;i++){
move(i-1,i);
}
move(n,1);
return dp[1][x]!=4;
}
void print(int x){
x=dp[1][x];
static int ans[N+1];
for(int i=n;i>=1;i--){
if(x==2||x==3){
ans[i]=i;
}
if(x==1||x==3){
int p=i-1;
if(!p){
p=n;
}
ans[p]=i;
}
x=dp[i][x];
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
cout<<'\n';
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
c[i]<<=1;
}
if(solve(0)){
print(0);
}else if(solve(1)){
print(1);
}else if(solve(2)){
print(2);
}else if(solve(3)){
print(3);
}else{
cout<<"NIE\n";
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
