fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long 
  5. #define pb push_back
  6. vector<ll> a,b,c,d,sum1,sum2;
  7. ll binary(vector<ll> A, ll low, ll high, ll x){
  8.     ll mid, result=-1;
  9.     while(low<=high){
  10.          mid = (low+high)/2;
  11.         if(A[mid]==x && (mid-1<0 || A[mid-1]<x))
  12.         {
  13.             result = mid;
  14.             break;
  15.         }
  16.         else if((A[mid]==x && A[mid-1]==x) || (x<A[mid]))
  17.         {
  18.             high = mid-1;
  19.         }
  20.         else
  21.         {
  22.             low = mid+1;
  23.         }
  24. 	//cout << " stuck " << endl;
  25.     }
  26.     return result;
  27. }
  28. ll binary1( vector<ll> A, ll low, ll high, ll x) {
  29.     ll mid , result =-1;
  30.     while(low<=high){
  31.          mid = (low+high)/2;
  32.          if(A[mid]==x && (mid+1==A.size() || A[mid+1]>x))
  33.          {
  34.              result = mid;
  35.              break;
  36.          }
  37.          else if((A[mid]==x && A[mid+1]==x) || (A[mid]<x))
  38.          {
  39.              low = mid+1;
  40.          }
  41.          else{
  42.              high = mid-1;
  43.          }
  44. 	//cout << " stuck1 " << endl;
  45.     }
  46.     return result;
  47. }
  48.  
  49.  
  50. int main() {
  51. 	freopen("input.txt","r",stdin);
  52. 	freopen("output.txt","w",stdout);
  53. 	int t, cases=0;
  54. 	cin >> t;
  55. 	while(t--) {
  56. 		long long n, k;
  57. 		cin >> n >> k;
  58. 		a.clear();
  59. 		b.clear();
  60. 		c.clear();
  61. 		d.clear();
  62. 		sum1.clear();
  63. 		sum2.clear();
  64. 		for(long long int i=0;i<n;i++) {
  65. 			long long int x;
  66. 			cin >> x;
  67. 			a.push_back(x);
  68. 		}
  69. 		for(long long int j=0;j<n;j++) {
  70. 			long long int x;
  71. 			cin >> x;
  72. 			b.push_back(x);
  73. 		}
  74. 		 for(long long int i=0;i<n;i++) {
  75.                         long long int x;
  76.                         cin >> x;
  77.                         c.push_back(x);
  78.                 }
  79.                 for(long long int j=0;j<n;j++) {
  80.                         long long int x;
  81.                         cin >> x;
  82.                         d.push_back(x);
  83.                 }
  84. 		for(ll i=0;i<n;i++) {
  85. 			for(ll j =0; j< n;j++) {
  86. 				sum1.pb((ll)((a[i]^b[j])));
  87. 			}
  88. 		}
  89. 		for(ll i=0;i<n;i++) {
  90. 			for(ll j=0;j<n;j++) {
  91. 				sum2.pb((ll)((c[i])^d[j]));
  92. 			}
  93. 		}
  94. 		//sort(sum1.begin(), sum1.end());
  95. 		sort(sum2.begin(), sum2.end());
  96. 		ll answer=0;
  97. 		cout << sum1.size() << endl;
  98. 		for(ll i=0;i<sum1.size();i++) {
  99. 			ll l1 = binary(sum2,0,sum2.size()-1, k^sum1[i]);
  100. 			ll l2 = binary1(sum2,0, sum2.size()-1,k^sum1[i]);
  101. 			if(l1!=-1 && l2!=-1){
  102. 				answer += (l2-l1+1);
  103. 			}
  104. 			//cout << " return " << endl;
  105. 		}
  106. 		cout << "Case #" << ++cases << ": " << answer << endl;
  107. 	}
  108. 	fclose(stdout);
  109. 	return 0;
  110.  
  111. }
  112.  
Time limit exceeded #stdin #stdout 5s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mk6Qya
language:
C++ (gcc 8.3)
created:
8 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!