-
Notifications
You must be signed in to change notification settings - Fork 0
/
1043.cpp
107 lines (100 loc) · 1.38 KB
/
1043.cpp
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
102
103
104
105
106
107
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1002
int out[N];
int a[N];
int n;
int flag;
int cnt;
int get_root(int s,int t){
int ret=0;
if(s>t)
return 0;
if(s==t){
out[cnt++]=a[s];
return 0;
}
if(flag==0){
int j=t+1;
for(int i=s+1;i<=t;i++)
if(a[i]>=a[s]){
j=i;
break;
}
ret=get_root(s+1,j-1);
if(ret==-1)
return -1;
for(int i=j;i<=t;i++)
if(a[i]<a[s]){
return -1;
}
ret = get_root(j,t);
if(ret==-1)
return -1;
out[cnt++]=a[s];
}else{
int j=t+1;
for(int i=s+1;i<=t;i++)
if(a[i]<a[s]){
j=i;
break;
}
ret=get_root(s+1,j-1);
if(ret==-1)
return -1;
for(int i=j;i<=t;i++)
if(a[i]>=a[s]){
return -1;
}
ret = get_root(j,t);
if(ret==-1)
return -1;
out[cnt++]=a[s];
}
}
int main(){
cnt=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
if(a[0]<=a[1])
flag=1;//right->left->root
else
flag=0;
//q.push(a[0]);
int ret;
ret = 0;
ret=get_root(0,n-1);
if(ret==-1){
printf("NO\n");
}else{
printf("YES\n%d",out[0]);
for(int i=1;i<cnt;i++)
printf(" %d",out[i]);
}
//system("PAUSE");
return 0;
}
/*
Sample Input 1:
7
8 6 5 7 10 8 11
Sample Output 1:
YES
5 7 6 8 11 10 8
Sample Input 2:
7
8 10 11 8 6 7 5
Sample Output 2:
YES
11 8 10 7 5 6 8
Sample Input 3:
7
8 6 8 5 10 9 11
Sample Output 3:
NO
*/