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