fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11. 	vector<int> a(n);
  12. 	vector<int> b;
  13.  
  14. 	for(int i = 0; i < n; i++){
  15. 		cin >> a[i];
  16. 		if(a[i] != -1)b.push_back(i);
  17. 	}
  18. 	if(b.size() == 0){
  19. 		if(a[0] == -1){
  20. 			int t = 1;
  21. 			for(int i = 0; i < n; i++){
  22. 				cout << t << " ";
  23. 				t = (t == 2 ? 1 : 2);
  24. 			}
  25. 			cout << "\n";
  26. 			return;
  27. 		}
  28. 		for(int i = 0; i < n - 1; i++){
  29. 			if(a[i] != a[i + 1] / 2 || a[i + 1] != a[i] / 2){
  30. 				cout << -1 << "\n";
  31. 				return;
  32. 			}
  33. 		}
  34.  
  35. 		for(auto x: a)cout << x << " ";
  36. 		cout << "\n";
  37.  
  38. 		return;
  39. 	}
  40.  
  41. 	int idx = b[0] - 1;
  42. 	while(idx >= 0){
  43. 		if(a[idx + 1] > 1)a[idx] = a[idx + 1] / 2;
  44. 		else a[idx] = 2;
  45. 		idx--;
  46. 	}
  47.  
  48. 	idx = b.back() + 1;
  49. 	while(idx < n){
  50. 		if(a[idx - 1] == 1)a[idx] = 2;
  51. 		else a[idx] = a[idx - 1] / 2;
  52. 		idx++;
  53. 	}
  54.  
  55. 	for(int i = 0; i < (int)b.size() - 1; i++){
  56. 		multiset<pair<int, int>> s;
  57. 		s.insert({a[b[i]], 0});
  58. 		s.insert({a[b[i + 1]], 1});
  59. 		int idx1 = b[i] + 1;
  60. 		int idx2 = b[i + 1] - 1;
  61. 		while(s.size() && idx1 <= idx2){
  62. 			auto [x, y] = *(s.rbegin());
  63. 			s.erase(s.find({x, y}));
  64. 			if(y == 0){
  65.  
  66. 				if(x == 1)a[idx1] = 2;
  67. 				else a[idx1] = x / 2;
  68. 				s.insert({a[idx1], 0});
  69. 				idx1++;
  70. 			}else{
  71.  
  72. 				if(x == 1)a[idx2] = 2;
  73. 				else a[idx2] = x / 2;
  74. 				s.insert({a[idx2], 1});
  75. 				idx2--;
  76.  
  77. 			}
  78.  
  79. 		}
  80. 	}
  81. 	for(int i = 0; i < n - 1; i++){
  82. 		if(a[i] != (a[i + 1] / 2) && a[i + 1] != (a[i] / 2)){
  83. 			cout << -1 << "\n";
  84. 			return;
  85. 			// break;
  86. 		}
  87. 	}
  88.  
  89. 	for(auto x: a)cout << x << " ";
  90. 	cout << "\n";
  91.  
  92. }
  93.  
  94. int main(){
  95. 	ios_base::sync_with_stdio(false);
  96. 	cin.tie(nullptr);
  97.  
  98. 	int t = 1;
  99. 	cin >> t;
  100.  
  101. 	for(int i = 1; i <= t; i++){
  102. 		solve();
  103. 	}
  104. 	return 0;
  105. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1
stdout
copy 
1 2 1 2 1 2 1 2 
1 2 1 2 
3 1 2 4 9 4 
-1
-1
-1
4 2 
1 3 1 3 6 
2 1 3 1 2 1 3 7 3 1 3 1 2
https://ideone.com/lXVwFv
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

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!