The problem link is : http://www.spoj.com/problems/IITWPC4D/
The solution link is : https://ideone.com/fAfVTL
I have tested my code for over 100 testcases and i found my code is working fine but still i am getting WA…
please if anyone can help me find a testcase for which my code fails… thank you
int a[100010], b[100010];
int main()
{
// ios_base::sync_with_stdio(false);
int t, n;
cin >> t;
set<int>::iterator it;
set<int>::reverse_iterator it1;
set<int> s;
for (int cs = 1; cs <= t; cs++) {
cout << "Test : " << cs << endl;
s.clear();
cin >> n;
bool f = true;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] > i) {
f = false;
}
}
if (!f) {
cout << -1 << endl;
continue;
}
int x = n;
for (int i = n - 1; i >= 0; i--) {
if (a[i] == 0) {
if (!s.empty()) {
it1 = s.rbegin();
b[i] = *it1;
it = s.find(*it1);
s.erase(it);
} else {
b[i] = x--;
}
} else if (s.size() == a[i]) {
b[i] = x--;
} else if (s.size() < a[i]) {
int y = a[i] - s.size();
for (int j = 0; j < y; j++) {
s.insert(x--);
}
b[i] = x--;
} else {
int y = s.size() - a[i];
it = s.lower_bound(*s.begin() - 1 + y);
b[i] = *it;
s.erase(it);
}
}
for (int i = 0; i < n; i++) {
cout << b[i] << " ";
}
cout << endl;
}
return 0;
}