fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <set>
  5. #include <assert.h>
  6. using namespace std;
  7.  
  8.  
  9.  
  10. long long readInt(long long l,long long r,char endd){
  11. 	long long x=0;
  12. 	int cnt=0;
  13. 	int fi=-1;
  14. 	bool is_neg=false;
  15. 	while(true){
  16. 		char g=getchar();
  17. 		if(g=='-'){
  18. 			assert(fi==-1);
  19. 			is_neg=true;
  20. 			continue;
  21. 		}
  22. 		if('0'<=g && g<='9'){
  23. 			x*=10;
  24. 			x+=g-'0';
  25. 			if(cnt==0){
  26. 				fi=g-'0';
  27. 			}
  28. 			cnt++;
  29. 			assert(fi!=0 || cnt==1);
  30. 			assert(fi!=0 || is_neg==false);
  31.  
  32. 			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  33. 		} else if(g==endd){
  34. 			assert(cnt>0);
  35. 			if(is_neg){
  36. 				x= -x;
  37. 			}
  38. 			assert(l<=x && x<=r);
  39. 			return x;
  40. 		} else {
  41. 			assert(false);
  42. 		}
  43. 	}
  44. }
  45. string readString(int l,int r,char endd){
  46. 	string ret="";
  47. 	int cnt=0;
  48. 	while(true){
  49. 		char g=getchar();
  50. 		assert(g!=-1);
  51. 		if(g==endd){
  52. 			break;
  53. 		}
  54. 		cnt++;
  55. 		ret+=g;
  56. 	}
  57. 	assert(l<=cnt && cnt<=r);
  58. 	return ret;
  59. }
  60. long long readIntSp(long long l,long long r){
  61. 	return readInt(l,r,' ');
  62. }
  63. long long readIntLn(long long l,long long r){
  64. 	return readInt(l,r,'\n');
  65. }
  66. string readStringLn(int l,int r){
  67. 	return readString(l,r,'\n');
  68. }
  69. string readStringSp(int l,int r){
  70. 	return readString(l,r,' ');
  71. }
  72.  
  73.  
  74. struct nd{
  75. 	nd * nxt[2];
  76. 	int sum;
  77. 	nd(){
  78. 		nxt[0]=nxt[1]=NULL;
  79. 		sum = 0;
  80. 	}
  81. };
  82. int T;
  83. int n,k,p;
  84. int sm_n = 0;
  85. set<int> g;
  86. int arr[1001001];
  87. nd * tree;
  88. long long bit_weight[35];
  89.  
  90. pair<long long,long long> A[100100],B[100100];
  91. int ca=0,cb =0 ;
  92. int main(){
  93. 	T=readIntLn(1,20);
  94. 	while(T--){
  95. 		n=readIntSp(1,1000000);
  96. 		k=readIntSp(1,30);
  97. 		p=readIntLn(1,1<<k);
  98. 		tree = new nd();
  99. 		g.clear();
  100. 		for(int i=0;i<k;i++){
  101. 			bit_weight[i]= 0;
  102. 		}
  103. 		for(int i=1;i<=n;i++){
  104. 			if(i==n){
  105. 				arr[i]=readIntLn(0,(1<<k)-1);
  106. 			} else {
  107. 				arr[i]=readIntSp(0,(1<<k)-1);
  108. 			}
  109. 			assert(g.count(arr[i])==0);
  110. 			g.insert(arr[i]);
  111. 		}
  112. 		long long inv=0;
  113. 		for(int i=1;i<=n;i++){
  114. 			nd * cur = tree;
  115. 			for(int j=k-1;j>=0;j--){
  116. 				if(arr[i] & (1<<j)){
  117. 					if(cur->nxt[0]!=NULL)
  118. 						bit_weight[j] += cur->nxt[0]->sum;
  119. 					if(cur->nxt[1] == NULL){
  120. 						cur->nxt[1] = new nd();
  121. 					}
  122. 					cur=cur->nxt[1];
  123. 				} else {
  124. 					if(cur->nxt[1]!=NULL){
  125. 						bit_weight[j] -= cur->nxt[1]->sum;
  126. 						inv += cur->nxt[1]->sum;
  127. 					}
  128. 					if(cur->nxt[0] == NULL){
  129. 						cur->nxt[0] = new nd();
  130. 					}
  131. 					cur=cur->nxt[0];
  132. 				}
  133. 				cur ->sum ++ ;
  134. 			}
  135. 		}
  136. 		ca = k/2;
  137. 		cb = k - k/2;
  138. 		for(int i=0;i<(1<<ca);i++){
  139. 			A[i].first = 0;
  140. 			A[i].second = i;
  141. 			for(int j=0;j<ca;j++){
  142. 				if(i & (1<<j)){
  143. 					A[i].first += bit_weight[j];
  144. 				}
  145. 			}
  146. 		}
  147. 		for(int i=0;i<(1<<cb);i++){
  148. 			B[i].first = 0;
  149. 			B[i].second = i;
  150. 			for(int j=0;j<cb;j++){
  151. 				if(i & (1<<j)){
  152. 					B[i].first += bit_weight[ca+j];
  153. 				}
  154. 			}
  155. 		}
  156. 		sort(A,A+(1<<ca));
  157.  
  158. 		sort(B,B+(1<<cb));
  159.  
  160. 		long long l=-1ll<<60,r=1ll<<60;
  161. 		long long vl=0,vr= 1<<k;
  162. 		while(r-l>1){
  163. 			long long m=(r+l)/2;
  164. 			long long cnt = 0;
  165. 			int pa = (1<<ca)-1;
  166. 			for(int i=0;i<(1<<cb);i++){
  167. 				while(pa>=0 && A[pa].first + B[i].first > m){
  168. 					pa --;
  169. 				}
  170. 				cnt += pa + 1;
  171. 			}
  172. 			if(cnt < p){
  173. 				l = m;
  174. 				vl = cnt;
  175. 			} else {
  176. 				r= m;
  177. 				vr = cnt;
  178. 			}
  179. 		}
  180. 		long long need = p - vl;
  181. 		int pa1=(1<<ca),pa2=(1<<ca);
  182. 		long long sol=0;
  183. 		for(int i=0;i<(1<<cb);i++){
  184. 			swap(B[i].first,B[i].second);
  185. 		}
  186.  
  187. 		sort(B,B+(1<<cb));
  188. 		for(int i=0;i<(1<<cb);i++){
  189. 			swap(B[i].first,B[i].second);
  190. 		}
  191. 		/*for(int i=0;i<(1<<ca);i++){
  192. 			cout<<A[i].first <<" "<<A[i].second<<endl;
  193. 		}
  194. 		cout<<endl;
  195. 		for(int i=0;i<(1<<cb);i++){
  196. 			cout<<B[i].first <<" "<<B[i].second<<endl;
  197. 		}
  198. 		cout<<endl;*/
  199. 		for(int i=0;i<(1<<cb);i++){
  200. 			int l1=-1,r1=1<<ca;
  201. 			while(r1 - l1 > 1){
  202. 				int m=(r1+l1)/2;
  203. 				if(A[m].first + B[i].first > r){
  204. 					r1=m;
  205. 				} else {
  206. 					l1=m;
  207. 				}
  208. 			}
  209. 			int l2=-1,r2=1<<ca;
  210. 			while(r2 - l2 > 1){
  211. 				int m=(r2+l2)/2;
  212. 				if(A[m].first + B[i].first >= r){
  213. 					r2=m;
  214. 				} else {
  215. 					l2=m;
  216. 				}
  217. 			}
  218. 			if(need > r1- r2){
  219. 				need -= r1 - r2;
  220. 			} else {
  221. 				sol = (B[i].second << ca) + A[r2 + need -1].second;
  222. 				break;
  223. 			}
  224. 		}
  225. 		cout<<sol<<endl;
  226. 	}
  227. 	assert(getchar()==-1);
  228. }
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
3
4 3 5
2 0 3 7
2 2 1
2 0
6 3 2
7 5 3 4 1 2
stdout
copy 
4
2
5
https://ideone.com/71pcrM
language:
C++14 (gcc 8.3)
created:
5 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!