fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 305; 
  5. int a[N][N];
  6. int prefix[N];
  7.  
  8. void solve() {
  9. 	cout << "---"<<endl;
  10. 	int n;
  11. 	cin >> n;
  12. 	for (int i = 0; i < n; i++) {
  13. 		for (int j = 0; j < n; j++) {
  14. 			cin >> a[i][j];
  15. 		}
  16. 	}
  17. 	vector<pair<int, int>> intervals;
  18. 	vector<bool> used(n + 1, false);
  19.  
  20. 	for (int i = 0; i < n; i++) {
  21. 		prefix[0] = 0;
  22. 		for (int j = 0; j < n; j++) {
  23. 			prefix[j + 1] = prefix[j];
  24. 			prefix[j + 1] += a[i][j];
  25. 		}
  26.  
  27. 		// binary search through prefix sum
  28. 		int l = 0, r = n - 1;
  29. 		if (i) r = n - 2; 
  30.  
  31. 		while (l < r) {
  32. 			int m = l + (r - l) / 2;
  33. 			int v = prefix[n] - prefix[m + 1];
  34. 			if (v < i) {
  35. 				r = m - 1;
  36. 			} else if (v > i) {
  37. 				l = m + 1;
  38. 			} else {
  39. 				// find first position to the right
  40. 				r = m;
  41. 				while (r < n && a[r] == 0) r++;
  42. 				r--;
  43. 				break;
  44. 			}
  45. 		}
  46.  
  47. 		if (l < r) {
  48. 			cout << i << endl;
  49. 			return;
  50. 		}
  51. 		else {
  52. 			if (l == r) {
  53. 				if (used[l]) {
  54. 					cout << i << endl;
  55. 					return;
  56. 				} else {
  57. 					used[l] = true;
  58. 				}
  59. 			} 
  60. 			intervals.push_back({l, r});
  61. 		}
  62. 	}
  63.  
  64. 	int first_free = 0;
  65. 	for (int i = 0; i < n; i++) {
  66. 		if (!used[i]) {
  67. 			first_free = i;
  68. 			break;
  69. 		}	
  70. 	}	
  71.  
  72. 	cout << "intervals: " << endl;
  73. 	for (int i = 0; i < intervals.size(); i++) {
  74. 		cout << intervals[i].first << " " << intervals[i].second << endl;
  75. 	}
  76. 	for (int i = 0; i < intervals.size(); i++) {
  77. 		if (intervals[i].first == intervals[i].second) continue;
  78.  
  79. 		if (intervals[i].first > first_free) {
  80. 			int k = intervals[i].first;
  81. 			while (k <= intervals[i].second && used[k]) {
  82. 				k++;
  83. 			} 
  84. 			if (k > intervals[i].second) {
  85. 				cout << i << endl;
  86. 				return;
  87. 			}
  88. 			else {
  89. 				used[k] = true;
  90. 			}
  91. 		} else {
  92. 			if (first_free > intervals[i].second) {
  93. 				cout << i << endl;
  94. 				return;
  95. 			} else {
  96. 				used[first_free] = true;
  97. 				while (first_free < n && used[first_free]) first_free++;
  98. 			}
  99. 		}
  100. 	}
  101. 	cout << n << endl;
  102. }
  103.  
  104. int main() {
  105. 	int t;
  106. 	cin >> t;
  107. 	while (t--) solve();
  108. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
3
2
10 10
10 10
3
2 3 3
4 4 1
2 1 1
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1
stdout
copy 
---
intervals: 
1 1
0 0
2
---
intervals: 
2 2
1 1
0 -1
2
---
2
https://ideone.com/1PHbNa
language:
C++14 (gcc 8.3)
created:
38 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!