https://vjudge.net/contest/301853#problem/A
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<string.h> 5 #include<algorithm> 6 using namespace std; 7 typedef long long ll; 8 int vis[100010][10]={0}; 9 int a[100010]; 10 int b[100010]; 11 int n; 12 int f; 13 int dfs(int x) 14 { 15 if(x==n) 16 { 17 return 1; 18 } 19 for(int i=1;i<=5;i++) 20 { 21 if(vis[x+1][i]!=1) 22 { 23 if((a[x]<a[x+1])&&b[x]<i||(a[x]>a[x+1]&&b[x]>i||a[x]==a[x+1]&&b[x]!=i)) 24 { 25 b[x+1]=i; 26 vis[x+1][i]=1; 27 if(dfs(x+1)) 28 { 29 return 1; 30 } 31 } 32 } 33 } 34 return 0; 35 } 36 int main() 37 { 38 cin>>n; 39 for(int i=1;i<=n;i++) 40 { 41 cin>>a[i]; 42 } 43 for(int i=1;i<=5;i++) 44 { 45 b[1]=i; 46 if(dfs(1)) 47 { 48 f=1; 49 break; 50 } 51 } 52 if(f==1) 53 { 54 for(int i=1;i<=n;i++) 55 { 56 printf("%d ",b[i]); 57 } 58 cout<<endl; 59 } 60 else 61 { 62 printf("-1 "); 63 } 64 return 0; 65 }