Summer Reading

Time Limit: 20 Sec  Memory Limit: 512 MB

Description

　　

Input

　　

Output

　　

Sample Input

　　7

　　0 1 0 0 0 3 0

Sample Output

　　3

　　1 1 2 2 3 3 3

HINT

　　

Solution

　　

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std;10 typedef long long s64;11 12 const int ONE = 1000005;13 const int MOD = 1e9 + 7;14 15 int n;16 int a[ONE];17 int vis[ONE], ans[ONE];18 19 struct power20 {21 int val, times;22 friend bool operator <(power a, power b)23 {24 if(a.val != b.val) return a.val < b.val;25 return a.times < b.times;26 }27 }low[ONE], up[ONE];28 29 int get() 30 { 31 int res;char c; 32 while( (c=getchar())<48 || c>57 );33 res=c-48; 34 while( (c=getchar())>=48 && c<=57 )35 res=res*10+c-48; 36 return res; 37 }38 39 void Deal_first()40 {41 low[1] = up[1] = (power){ 1, 1};42 for(int i = 2; i <= n; i++)43 {44 low[i] = low[i - 1], up[i] = up[i - 1];45 46 if(++low[i].times > 5) low[i] = (power){low[i].val + 1, 1};47 if(++up[i].times > 2) up[i] = (power){up[i].val + 1, 1};48 49 if(a[i] != 0)50 {51 if(low[i].val > a[i] || up[i].val < a[i])52 {53 printf("-1");54 exit(0);55 }56 low[i] = max(low[i], (power){a[i], 1});57 up[i] = min(up[i], (power){a[i], 5});58 }59 60 if(low[i].val > up[i].val) {printf("-1"); exit(0);}61 }62 }63 64 int main()65 {66 n = get();67 for(int i = 1; i <= n; i++)68 a[i] = get();69 if(a[1] > 1) {printf("-1"); exit(0);}70 Deal_first();71 72 int val = up[n].val - (up[n].times == 1);73 if(low[n].val > val) {printf("-1"); exit(0);}74 for(int i = n; i >= 1; i--)75 {76 val = min(val, up[i].val);77 val -= vis[val] == 5;78 ans[i] = val, vis[val]++;79 }80 81 if(ans[1] <= 0) {printf("-1"); exit(0);}82 83 printf("%d\n", ans[n]);84 for(int i = 1; i <= n; i++)85 printf("%d ", ans[i]);86 87 }