fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200;
  5.  
  6. int n, par[N], sz[N], q = 0, a = 0, b = 0;
  7.  
  8. int find(int v) {
  9. 	return par[v] == v ? v : (par[v] = find(par[v]));
  10. }
  11.  
  12. bool merge(int u, int v) {
  13. 	u = find(u), v = find(v);
  14. 	if(u == v) return 0;
  15.  
  16. 	par[v] = u;
  17. 	sz[u] += sz[v];
  18. 	return 1;
  19. }
  20.  
  21. bool found(int p, int l, int x) {
  22. 	vector<int> ask(n + 1);
  23. 	ask[p] = 1;
  24. 	int edges = 0;
  25. 	for(int i = l + 1; i <= x; i++) {
  26. 		if(find(i) != find(p)) {
  27. 			ask[i] = 2;
  28. 			edges++;
  29. 		}
  30. 	}
  31. 	q++;
  32. 	if(q > 2000) assert(0);
  33. 	cout << "? ";
  34. 	for(int i = 1; i <= n; i++) {
  35. 		cout << ask[i] << " ";
  36. 	}
  37. 	cout << endl;
  38.  
  39. 	int z;
  40. 	cin >> z;
  41. 	return z < b * edges;
  42. }	
  43.  
  44. int main() {
  45. 	cin.tie(0); ios_base::sync_with_stdio(0);
  46.  
  47. 	cin >> n;
  48.  
  49. 	for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
  50.  
  51. 	cout << "? 1 2 ";
  52. 	for(int i = 3; i <= n; i++) cout << "0 ";
  53. 	cout << endl;
  54.  
  55. 	cin >> a; 
  56.  
  57. 	for(int i = 1; i <= n && b == 0; i++) {
  58. 		cout << "? ";
  59. 		for(int j = 1; j <= n; j++) {
  60. 			if(i != j) cout << 2 << " ";
  61. 			else cout << 1 << " ";
  62. 		}
  63. 		cout << endl;
  64.  
  65. 		int z;
  66. 		cin >> z;
  67.  
  68. 		if(a * (n - 1) != z) {
  69. 			for(int j = 1; j <= n; j++) {
  70. 				if(i == j) continue;
  71. 				vector<int> ask(n + 1);
  72. 				ask[i] = 1;
  73. 				ask[j] = 2;
  74. 				cout << "? ";
  75. 				for(int i = 1; i <= n; i++) {
  76. 					cout << ask[i] << " ";
  77. 				}
  78. 				cout << endl;
  79. 				int y;
  80. 				cin >> y;
  81. 				if(y != a) {
  82. 					b = y;
  83. 					break;
  84. 				}
  85. 			}
  86. 			if(a > b) swap(a, b);
  87. 		}
  88.  
  89.  
  90. 	}
  91.  
  92. 	if(b == 0) {
  93. 		cout << "! " << n - 1 << '\n';
  94. 		for(int i = 2; i <= n; i++) {
  95. 			cout << 1 << " " << i << '\n';
  96. 		}
  97. 		cout << flush;
  98.  
  99. 		return 0;
  100. 	}
  101.  
  102. 	// cout << a << " " << b << endl;
  103.  
  104.  
  105.  
  106. 	int ones = 0;
  107. 	vector<pair<int,int>> edges;
  108. 	for(int i = 1; i <= n && ones < n - 1; i++) {
  109. 		int z = i;
  110. 		while(1) {
  111. 			int l = z + 1, r = n, x = -1;
  112. 			while(l <= r) {
  113. 				int mid = (l + r) / 2;
  114. 				if(found(i, z, mid)) {
  115. 					r = mid - 1, x = mid; 
  116. 				} else {
  117. 					l = mid + 1;
  118. 				}
  119. 			}
  120. 			z = x;
  121. 			ones += x != -1;
  122. 			if(x == -1) break;
  123. 			edges.push_back({i, x});
  124. 			merge(i, x);
  125. 			if(ones == n - 1) break;
  126. 		}
  127. 	}
  128.  
  129. 	cout << "! " << n - 1 << '\n';
  130.  
  131. 	set<int> parents;
  132. 	for(int i = 1; i <= n; i++) {
  133. 		parents.insert(find(i));
  134. 	}
  135.  
  136. 	for(int i = 1; i <= n && edges.size() < n - 1; i++) {
  137. 		if(merge(find(i), *parents.begin())) {
  138. 			edges.push_back({*parents.begin(), find(i)});
  139. 			assert(*parents.begin() < find(i));
  140. 		}
  141. 	}
  142.  
  143. 	assert(edges.size() == n - 1);
  144. 	for(auto [u, v] : edges) {
  145. 		if(u > v) cout << v << " " << u << '\n';
  146. 		else cout << u << " " << v << '\n';
  147. 	}
  148. 	cout << flush;
  149.  
  150. }
Success #stdin #stdout 0.01s 5572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
? 1 2 
! -1
https://ideone.com/VjElm6
language:
C++ (gcc 8.3)
created:
326 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!