fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define REP(i,n) for (int i = 1; i <= n; i++)
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define ii pair<int,int>
  8. #define vi vector<int>
  9. #define vii vector<ii>
  10. #define lli long long int
  11. #define INF 1000000000
  12. #define endl '\n'
  13. const double PI = 3.141592653589793238460;
  14. typedef std::complex<double> Complex;
  15. typedef std::valarray<Complex> CArray;
  16.  
  17. using namespace std;
  18.  
  19. int ar[100010] , br[100010];
  20. vi tmpA , tmpB;
  21.  
  22. bool init(int n , string A , string B)
  23. {
  24. 	REP(i , n+2) ar[i] = br[i] = 0;
  25.  
  26. 	int i = n+2;
  27. 	while(A.size() > 0)
  28. 	ar[i] = A.back() - '0' , A.pop_back() , i--;
  29.  
  30. 	bool hasB = 0;
  31. 	i = n+2;
  32. 	while(B.size() > 0)
  33. 	br[i] = B.back() - '0' , hasB |= br[i] , B.pop_back() , i--;
  34.  
  35. 	return hasB;
  36. }
  37.  
  38. bool modifyABOnce(int n)
  39. {
  40. 	tmpA.resize(n+3) , tmpB.resize(n+3);
  41. 	REP(i , n+2) tmpA[i] = 0 , tmpB[i] = 0;
  42.  
  43. 	REP(i , n+2) tmpA[i] = ar[i] ^ br[i];
  44.  
  45. 	bool hasB = 0;
  46. 	for(int i=2;i<=n+1;i++)
  47. 	tmpB[i] = ar[i+1] & br[i+1] , hasB |= tmpB[i];
  48.  
  49. 	REP(i , n+2) ar[i] = tmpA[i];
  50. 	REP(i , n+2) br[i] = tmpB[i];
  51.  
  52. 	return hasB;
  53. }
  54.  
  55. bool modifyABAgain(int n)
  56. {
  57. 	tmpA.resize(n+3) , tmpB.resize(n+3);
  58. 	REP(i , n+2) tmpA[i] = 0 , tmpB[i] = 0;
  59.  
  60. 	REP(i , n+2) tmpA[i] = ar[i] ^ br[i];
  61.  
  62. 	bool hasB = 0;
  63. 	for(int i=1;i<=n+1;i++)
  64. 	tmpB[i] = ar[i+1] & br[i+1] , hasB |= tmpB[i];
  65.  
  66. 	REP(i , n+2) ar[i] = tmpA[i];
  67. 	REP(i , n+2) br[i] = tmpB[i];
  68.  
  69. 	return hasB;
  70. }
  71.  
  72.  
  73. int getMeAns(int n)
  74. {
  75. 	int ans = 0;
  76. 	int cnt = 0;
  77.  
  78. 	for(int i=1;i<=n+2;i++)
  79. 	{
  80. 		if(ar[i] == 0) cnt = 0;
  81. 		else		   cnt++;
  82.  
  83. 		if(br[i] == 1)
  84. 		{
  85. 			ans = max(ans , cnt);
  86. 			if(cnt == 0) cnt = 1;
  87. 			else		 cnt = 0;
  88. 		}
  89. 	}
  90.  
  91. 	return ans + 1;
  92. }
  93.  
  94. int main()
  95. {
  96. 	int t , n , cnt;
  97. 	string A , B;
  98. 	bool hasB;
  99.  
  100. 	cin>>t;
  101. 	while(t--)
  102. 	{
  103. 		cin>>A>>B , n = max(A.size() , B.size()) , cnt = 0;
  104. 		hasB = init(n , A , B);
  105.  
  106. 		if(!hasB)
  107. 		{
  108. 			cout<<cnt<<endl;
  109. 			continue;
  110. 		}
  111.  
  112. 		cnt++;
  113. 		hasB = modifyABOnce(n);
  114.  
  115.  
  116. 		if(!hasB)
  117. 		{
  118. 			cout<<cnt<<endl;
  119. 			continue;
  120. 		}
  121.  
  122. 		cnt++;
  123. 		hasB = modifyABAgain(n);
  124.  
  125. 		if(!hasB)
  126. 		{
  127. 			cout<<cnt<<endl;
  128. 			continue;
  129. 		}
  130.  
  131. 		cout<<cnt+getMeAns(n)<<endl;
  132. 	}
  133. }
  134.  
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
1
1010
0001
stdout
copy 
1
https://ideone.com/Cuc42U
BINADD : Dec long challenge 2019
language:
C++14 (gcc 8.3)
created:
4 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!