fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <set>
  9. #include <queue>
  10. #include <stack>
  11. #include <cstdlib>
  12. #include <string>
  13. #include <list>
  14. #include <bitset>
  15. #include <iomanip>
  16. #include <cmath>
  17. #include <sstream>
  18. #include <deque>
  19. #include <climits>
  20. #include <cassert>
  21.  
  22. using namespace std;
  23.  
  24. #define ull unsigned long long
  25. #define ll long long
  26. #define Max(x,y) ((x)>(y)?(x):(y))
  27. #define Min(x,y) ((x)<(y)?(x):(y))
  28. #define Sl(x) scanf("%lld",&x)
  29. #define Su(x) scanf("%llu",&x)
  30. #define S(x) scanf("%d",&x)
  31. #define IS(x) cin>>x
  32. #define ISF(x) getline(cin,x)
  33. #define pii pair<int,int>
  34. #define pll pair<ll,ll>
  35. #define pps pair<ll,pll>
  36. #define ppf pair<pll,ll>
  37. #define psi pair<string,int>
  38. #define pis pair<int,string>
  39. #define fr first
  40. #define se second
  41. #define MOD 1000000007
  42. #define MP(x,y) make_pair(x,y)
  43. #define eps 1e-7
  44. #define V(x) vector<x>
  45. #define pb(x) push_back(x)
  46. #define mem(x,i) memset(x,i,sizeof(x))
  47. #define fori(i,s,n) for(i=(s);i<(n);i++)
  48. #define ford(i,s,n) for(i=(n);i>=(s);--i)
  49. #define INF 8944674407370955161LL
  50. #define debug(i,st,arr) fori(i,0,st){cout<<arr[i]<<" ";}cout<<endl;
  51. #define forci(i,sw) for((i)=(sw).begin();(i)!=(sw).end();(i)++)
  52. #define forcd(i,sw) for((i)=(sw).rbegin();(i)!=(sw).rend();(i)++)
  53.  
  54. int abs(int x) {if(x < 0) return -x; return x;}
  55.  
  56. int a[100010], b[100010];
  57.  
  58. int main()
  59. {
  60. //	ios_base::sync_with_stdio(false);
  61. 	int t, n;
  62. 	cin >> t;
  63. 	set<int>::iterator it;
  64. 	set<int>::reverse_iterator it1;
  65. 	set<int> s;
  66. 	for (int cs = 1; cs <= t; cs++) {
  67. 		cout << "Test : " << cs << endl;
  68. 		s.clear();
  69. 		cin >> n;
  70. 		bool f = true;
  71. 		for (int i = 0; i < n; i++) {
  72. 			//a[i] = rand()%(i+1);
  73. 			//cout << a[i] << " ";
  74. 			cin >> a[i];
  75. 			if (a[i] > i) {
  76. 				f = false;
  77. 			}
  78. 		}
  79. 		//cout << endl;
  80. 		if (!f) {
  81. 			cout << -1 << endl;
  82. 			continue;
  83. 		}
  84. 		int x = n;
  85. 		for (int i = n - 1; i >= 0; i--) {
  86. 			if (a[i] == 0) {
  87. 				if (!s.empty()) {
  88. 					it1 = s.rbegin();
  89. 					b[i] = *it1;
  90. 					it = s.find(*it1);
  91. 					s.erase(it);
  92. 				} else {
  93. 					b[i] = x--;
  94. 				}
  95. 			} else if (s.size() == a[i]) {
  96. 				b[i] = x--;
  97. 			} else if (s.size() < a[i]) {
  98. 				int y = a[i] - s.size();
  99. 				for (int j = 0; j < y; j++) {
  100. 					s.insert(x--);
  101. 				}
  102. 				b[i] = x--;				
  103. 			} else {
  104. 				int y = s.size() - a[i];
  105. 				it = s.lower_bound(*s.begin() - 1 + y);
  106. 				b[i] = *it;
  107. 				s.erase(it);
  108. 			}
  109. 		}
  110. 		for (int i = 0; i < n; i++) {
  111. 			cout << b[i] << " ";
  112. 		}
  113. 		cout << endl;
  114. 	}
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 4216KB
comments (?)
stdin
copy 
2
7
0 0 0 2 2 4 0
stdout
copy 
Test : 1
1 5 6 3 4 2 7 
Test : 2
1 5 6 3 4 2 7
https://ideone.com/fAfVTL
language:
C++ (gcc 8.3)
created:
10 years 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!