Codeforces Round #522 (Div. 2, based on Technocup 2019 Elimination Round 3) C. Playing Piano

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 #define arr(zzz) array<ll,zzz>
10 #define ll long long 
11 using namespace std;
12 const int maxn=1e6+100;
13 int a[maxn];
14 int vis[maxn][10];
15 int n;
16 int ans[maxn];
17 bool dfs(int x){//5*(5e5)
18     if(x==n)return 1;
19     for(int i=1;i<=5;i++){
20         if(vis[x+1][i])continue;
21         if((a[x+1]>a[x]&&i>ans[x])||(a[x+1]<a[x]&&i<ans[x])||(a[x+1]==a[x]&&i!=ans[x])){
22             vis[x+1][i]=1;
23             ans[x+1]=i;
24                 if(dfs(x+1))return 1;
25         }
26     }
27     return 0;
28 }
29 
30 int main(){
31     scanf("%d",&n);
32     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
33     for(int i=1;i<=5;i++){
34         ans[1]=i;
35         vis[1][i]=1;
36         if(dfs(1)){
37         for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
38                 return 0;
39         }
40 
41     }
42     cout<<-1<<endl;
43     return 0;
44 }