Problem: http://codeforces.com/contest/1262/problem/B
Solution:
- Verify data correctness while reading input data. Legismate data must be in a non-decreasing sequence.
- if (arr[i] < i || arr[i] < arr[i-1]) {flag = false;}
- Variable “mx” is used to record the maximum value that has occurred before.
- queue <int> q; keeps “less than the current maximum” but has not yet used numbers (sorted in an ascending order).
- Whenever possible, use numbers in the queue.
Explanation with example data:
arr[] = [0, 1, 3, 4, 5, 5]
mx = 0, arr[1] = 1, output: 1 (q = [])
mx = 1, arr[2] = 3, output: 3 (q = [2])
mx = 3, arr[3] = 4, output: 4 (q = [2])
mx = 4, arr[4] = 5, output: 5 (q = [2])
mx = 5, arr[5] = 5, output: 2 (q = [])
#include <iostream>
#include <queue>
using namespace std;
int arr[100005];
queue <int> q;
int t, n, mx, i;
bool flag;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> t){
while (t--){
cin >> n;
flag = true;
arr[0] = 0;
for (i = 1; i <= n; i++){
cin >> arr[i];
if (arr[i] < i || arr[i] < arr[i-1]){
flag = false;
}
}
if (!flag) cout << -1 << "\n";
else{
mx = 0;
for (i = 1; i <= n; i++){
if (i != 1) cout << " ";
if (arr[i] > mx){
cout << arr[i];
for (int j = mx+1; j < arr[i]; j++){
q.push(j);
}
mx = arr[i];
}else{
cout << q.front();
q.pop();
}
}
cout << "\n";
}
}
cout << "\n";
}
return 0;
}