fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include "library.h"
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. #define fi first
  12. #define se second
  13. #define mp make_pair
  14. #define pb push_back
  15. #define fbo find_by_order
  16. #define ook order_of_key
  17.  
  18. typedef long long ll;
  19. typedef pair<ll,ll> ii;
  20. typedef vector<int> vi;
  21. typedef long double ld; 
  22. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  23. typedef set<ll>::iterator sit;
  24. typedef map<ll,ll>::iterator mit;
  25.  
  26. vector<int> res;
  27. set<int> rem;
  28. int n;
  29.  
  30. int query(vector<int> &test)
  31. {
  32. 	int ex1=0;
  33. 	for(int i=0;i<n;i++)
  34. 	{
  35. 		if(test[i]) ex1=1;
  36. 	}
  37. 	if(!ex1) return 0;
  38. 	else return Query(test);
  39. }
  40.  
  41. void solve(int l, int r)
  42. {
  43. 	//cerr<<"SOLVE "<<l<<' '<<r<<'\n';
  44. 	if(l>r) return ;
  45. 	if(l==r)
  46. 	{
  47. 		res[l] = (*rem.begin()); return ;
  48. 	}
  49. 	int xr=0;
  50. 	for(int i=0;i<10;i++)
  51. 	{
  52. 		vector<int> test(n,0);
  53. 		for(int x:rem)
  54. 		{
  55. 			if(x&(1<<i))
  56. 			{
  57. 				test[x]=1;
  58. 			}
  59. 		}
  60. 		int res = query(test);
  61. 		test.assign(n,0);
  62. 		for(int x:rem)
  63. 		{
  64. 			if(!(x&(1<<i)))
  65. 			{
  66. 				test[x]=1;
  67. 			}
  68. 		}
  69. 		int res2 = query(test);
  70. 		if(res==res2)
  71. 		{
  72. 			xr^=(1<<i);
  73. 		}
  74. 	}
  75. 	set<int> possibleX; vi V;
  76. 	for(int x:rem)
  77. 	{
  78. 		if(possibleX.find(x^xr)==possibleX.end())
  79. 		{
  80. 			possibleX.insert(x); V.pb(x);
  81. 		}
  82. 	}
  83. 	int lo=0; int hi=int(V.size())-1;
  84. 	int ans = -1;
  85. 	while(lo<=hi)
  86. 	{
  87. 		int mid=(lo+hi)>>1;
  88. 		vector<int> test(n,0);
  89. 		for(int i=0;i<V.size();i++)
  90. 		{
  91. 			if(i<=mid) test[V[i]]=1;
  92. 			else test[V[i]]=0;
  93. 		}
  94. 		int ans1 = query(test);
  95. 		for(int x:rem)
  96. 		{
  97. 			test[x]^=1;
  98. 		}
  99. 		int ans2=query(test);
  100. 		if(ans1==ans2)
  101. 		{
  102. 			ans=mid;
  103. 			hi=mid-1;
  104. 		}
  105. 		else lo=mid+1;
  106. 	}
  107. 	//cerr<<"XOR : "<<xr<<'\n'; //cerr<<"ANS : "<<ans<<'\n';
  108. 	int x = V[ans]; int y = V[ans]^xr;
  109. 	if(l>0)
  110. 	{
  111. 		vector<int> test(n,0);
  112. 		test[res[l-1]]=1; test[x]=1;
  113. 		if(query(test)!=1)
  114. 		{
  115. 			swap(x,y);
  116. 		}
  117. 	}
  118. 	res[l] = x; res[r] = y;
  119. 	//cerr<<l<<' '<<x<<'\n'; //cerr<<r<<' '<<y<<'\n';
  120. 	rem.erase(x); rem.erase(y);
  121. 	solve(l+1,r-1);
  122. }
  123.  
  124. void Solve(int N)
  125. {
  126. 	n=N;
  127. 	res.resize(N);
  128. 	for(int i=0;i<N;i++) rem.insert(i);
  129. 	solve(0,N-1);
  130. 	for(int i=0;i<N;i++) res[i]++;
  131. 	Answer(res);
  132. }
  133.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:3:21: fatal error: library.h: No such file or directory
 #include "library.h"
                     ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/fCiLrs
language:
C++14 (gcc 8.3)
created:
6 years 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!