fork download 
  1. #include <bits/stdc++.h>
  2. #define LSOne(s) ((S) & (-S))
  3.  
  4. using namespace std;
  5. typedef long long int ll;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. typedef vector<bool> vb;
  9. typedef vector<vi> vvi;
  10. typedef vector<vll> vvll;
  11. typedef vector<vb> vvb;
  12.  
  13. void solve(){
  14.     ll n,i,a,k,t,m,actual,ini,fin;
  15.     cin>>n;
  16.     vector<pair<ll,ll> > datos(n);
  17.     for(i=0;i<n;i++){
  18.         cin>>datos[i].first;
  19.         datos[i].second=i;
  20.     }
  21.     ll conteo=0;
  22.     vector<ll> elementos(n);
  23.     sort(datos.begin(),datos.end());
  24.     conteo=0;
  25.     actual=n;
  26.     ini=0;
  27.     fin=n;
  28.     bool posible=1;
  29.     ll aux;
  30.     ll positivos=0;
  31.     while(ini<fin && actual>0){
  32.         if(conteo<datos[ini].first && ini<fin){
  33.             while(conteo<datos[ini].first && ini<fin){
  34.                 aux = fin;
  35.                 while(fin>0 && datos[fin-1].first==datos[fin-2].first){
  36.                     elementos[datos[fin-1].second]=actual;
  37.                     fin--;
  38.                     conteo++;
  39.                     positivos++;
  40.                 }
  41.                 if(fin-ini+positivos!=datos[fin-1].first){
  42.                     posible=0;
  43.                 }
  44.                 elementos[datos[fin-1].second]=actual;
  45.                 fin--;
  46.                 conteo++;
  47.                 positivos++;
  48.             }
  49.             actual--;
  50.         }
  51.         if(ini>=fin)continue;
  52.         if(actual==0){
  53.             posible=0;
  54.             continue;
  55.         }
  56.         if(conteo==datos[ini].first){
  57.             while(datos[ini].first==datos[ini+1].first && ini<fin-1){
  58.                 elementos[datos[ini].second]=-actual;
  59.                 ini++;
  60.             }
  61.             elementos[datos[ini].second]=-actual;
  62.             ini++;
  63.         }else{
  64.             posible=0;
  65.         }
  66.         actual--;
  67.     }
  68.     if(posible){
  69.         cout<<"YES\n";
  70.         for(i=0;i<n;i++){
  71.             cout<<elementos[i]<<" ";
  72.         }
  73.         cout<<"\n";
  74.     }else{
  75.         cout<<"NO\n";
  76.     }
  77. }
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  82.     ll t;
  83.     cin>>t;
  84.     while(t--)solve();
  85.     return 0;
  86. }
Runtime error #stdin #stdout #stderr 0.01s 5504KB
comments (?)
stdin 

35
3
1 1 3 
2
2 0 
6
5 0 3 1 5 5 
1
1 
1
0 
3
0 2 1 
3
0 0 0 
4
2 4 0 0 
3
1 1 0 
2
0 1 
2
1 2 
5
3 4 3 1 2 
1
1 
6
0 1 1 2 1 0 
3
0 2 3 
1
0 
6
5 2 0 1 0 1 
4
3 1 3 3 
2
2 2 
2
2 2 
3
1 1 0 
6
2 6 6 1 3 1 
3
0 3 0 
6
5 0 6 4 5 3 
1
0 
3
2 2 3 
2
0 0 
5
5 5 1 4 4 
4
3 2 2 1 
7
6 4 3 6 0 5 7 
7
0 0 1 0 6 4 3 
4
4 1 1 0 
2
2 1 
6
6 3 4 6 1 1 
2
0 2
stdout 
Standard output is empty
stderr 
prog: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
https://ideone.com/Zkjx7W
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!