fork download 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")  
  3. #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  4. using namespace std;
  5.  
  6. #define ll long long
  7. #define vll vector<ll>
  8. #define all(x) x.begin(),x.end()
  9. #define fo(i,a,b) for(ll i=a;i<=b;++i)
  10. #define fast ios::sync_with_stdio(0);cin.tie(0);
  11.  
  12. ll n;
  13.  
  14. void input(){
  15.     cin>>n;
  16.     vll f(n+1);
  17.     fo(i,1,n)cin>>f[i];
  18.  
  19.     if(f[1]!=0){
  20.         cout<<-1;
  21.         return;
  22.     }
  23.  
  24.     string S(n+1,' ');
  25.     S[1]='a';
  26.     vll pi(n+1,0);
  27.     pi[1]=0;
  28.     bool valid=true;
  29.  
  30.     fo(i,2,n){
  31.         if(f[i]>0){
  32.             char c=S[f[i]];
  33.             ll j=pi[i-1];
  34.             while(j>0&&S[j+1]!=c) j=pi[j];
  35.             if(S[j+1]==c) j++;
  36.             if(j!=f[i]){
  37.                 valid=false;
  38.                 break;
  39.             }
  40.             S[i]=c;
  41.             pi[i]=j;
  42.         } else {
  43.             bool found=false;
  44.             for(char c='a';c<='z';c++){
  45.                 ll j=pi[i-1];
  46.                 while(j>0&&S[j+1]!=c) j=pi[j];
  47.                 if(S[j+1]==c) j++;
  48.                 if(j==0){
  49.                     S[i]=c;
  50.                     pi[i]=0;
  51.                     found=true;
  52.                     break;
  53.                 }
  54.             }
  55.             if(!found){
  56.                 valid=false;
  57.                 break;
  58.             }
  59.         }
  60.     }
  61.  
  62.     cout<<(valid ? S.substr(1) : "-1");
  63. }
  64.  
  65. int main(){
  66.     freopen("PREFIX.inp","r",stdin);
  67.     freopen("PREFIX.out","w",stdout);
  68.     fast
  69.     input();
  70. }
  71.  
Success #stdin #stdout 0.01s 5272KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2WyYXp
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!