fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define vt vector<ll>
  5. #define vvt vector<vt>
  6. #define all(a) a.begin(), a.end()
  7. #define pb push_back
  8.  
  9. void print(vt &a){
  10. 	for(auto val: a)
  11. 		cout<<val<<" ";
  12. 	cout<<endl;
  13. }
  14.  
  15. void read(vt &a){
  16. 	for(int i=0;i<a.size();i++)
  17. 		cin>>a[i];
  18. }
  19.  
  20. void solve(){
  21. 	ll n;
  22. 	cin>>n;
  23. 	vvt a(n+1, vt(n+1,0));
  24. 	vt out(n+1, 0);
  25.  
  26. 	for(int i=2;i<=n;i++)
  27. 	for(int j=2;j<=n;j++){
  28. 		if(i==j)
  29. 		continue;
  30. 		cout<<"? 3 "<<1<<" "<<i<<" "<<j<<endl;
  31. 		ll ans;
  32. 		cin>>ans;
  33. 		a[i][j]|=ans;
  34. 	}
  35. 	for(int j=2;j<=n;j++)
  36. 		a[1][j]=1;
  37.  
  38. 	for(int i=1;i<=n;i++){
  39. 		for(int j=1;j<=n;j++)
  40. 			out[i]+=a[i][j];
  41. 	}
  42.  
  43. 	vt topo(n+1);
  44. 	ll cur=1;
  45. 	for(int i=1;i<=n;i++){
  46. 		for(int val=1;val<=n;val++){
  47. 			if(out[val]==0){
  48. 				topo[val]=cur;
  49. 				out[val]=-1;
  50. 				cur++;
  51. 				for(int par=1;par<=n;par++){
  52. 					if(a[par][val]){
  53. 						out[par]--;
  54. 					}
  55. 				}
  56. 				break;
  57. 			}
  58. 		}
  59. 	}
  60.  
  61. 	vvt edge;
  62. 	for(int i=2;i<=n;i++){
  63. 		ll mn=INT_MAX;
  64. 		ll ans=-1;
  65. 		for(int par=1;par<=n;par++){
  66. 			if(a[par][i]){
  67. 				if(topo[par]<mn){
  68. 					mn = topo[par];
  69. 					ans=par;
  70. 				}
  71. 			}
  72. 		}
  73.  
  74. 		if(ans!=-1)
  75. 			edge.pb({ans, i});
  76. 	}
  77.  
  78. 	cout<<"!"<<endl;
  79. 	for(auto val: edge)
  80. 	print(val);
  81. }
  82.  
  83. int main() {
  84. 	// your code goes here
  85. 	ll t;
  86.  
  87. 	cin>>t;
  88. 	while(t--){
  89. 		solve();
  90. 	}
  91. 	return 0;
  92. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
1
3
0
1
stdout
copy 
? 3 1 2 3
? 3 1 3 2
!
3 2 
1 3
https://ideone.com/Drkog7
language:
C++14 (gcc 8.3)
created:
2 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!