pratiyush7

Untitled

Mar 23rd, 2022
877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void mainSolve()
  5. {
  6.   int n;
  7.   cin >> n;
  8.   vector<int> B(n + 1, 0);
  9.   for (int i = 1; i <= n; i++)
  10.     cin >> B[i];
  11.   int maxi = -1;
  12.   for (int i = 1; i <= n; i++)
  13.   {
  14.     if (B[i] >= 0)
  15.     {
  16.       if (B[i] == maxi)
  17.         B[i] = -1;
  18.       else
  19.       {
  20.         if (maxi > B[i])
  21.         {
  22.           cout << -1 << '\n';
  23.           return;
  24.         }
  25.         maxi = B[i];
  26.       }
  27.     }
  28.   }
  29.   vector<int> A(n + 1, -1);
  30.   set <int> slots;
  31.   for (int i = 1; i <= n + 10; i++)
  32.   {
  33.     slots.insert(i);
  34.   }
  35.   set <int> elements;
  36.   for (int i = 0; i <= n + 10; i++)
  37.     elements.insert(i);
  38.   for (int i = 1; i <= n; i++)
  39.   {
  40.     if (B[i] >= 0)
  41.       elements.erase(B[i]);
  42.   }
  43.   bool first_time = true;
  44.   maxi = -1;
  45.   for (int i = 1; i <= n; i++)
  46.   {
  47.     if (B[i] == -1)
  48.       continue;
  49.     if (!first_time)
  50.     {
  51.       A[i] = maxi;
  52.       slots.erase(i);
  53.     }
  54.     else
  55.       first_time = false;
  56.     while (true)
  57.     {
  58.       auto it = elements.begin();
  59.       if ((*it) >= B[i])
  60.         break;
  61.       int l = (*slots.begin());
  62.       if (l > i)
  63.       {
  64.         cout << -1 << '\n';
  65.         return;
  66.       }
  67.       A[l] = (*it);
  68.       slots.erase(l);
  69.       elements.erase(it);
  70.     }
  71.     maxi = B[i];
  72.   }
  73.   for (int i = 1; i <= n; i++)
  74.   {
  75.     if (A[i] == -1)
  76.       A[i] = n + 5;
  77.   }
  78.   for (int i = 1; i <= n; i++)
  79.     cout << A[i] << ' ';
  80.   cout << '\n';
  81. }
  82.  
  83. int main()
  84. {
  85.   int t;
  86.   cin >> t;
  87.   while (t--)
  88.   {
  89.     mainSolve();
  90.   }
  91.   return 0;
  92. }
Add Comment
Please, Sign In to add comment