fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29.  
  30. string a;
  31.  
  32. int consistency1(int n){
  33.  
  34.     int ones = 0;
  35.     for(int i=0; i<n; i++) if(a[i] == '1') ones++;
  36.     int zeroes = n-ones;
  37.  
  38.     if(ones == zeroes) return n;
  39.  
  40.     unordered_map<int, int> first = {{0, -1}};
  41.     unordered_map<int, int> second;
  42.  
  43.     int sum = 0;
  44.     int maxLen = 0;
  45.  
  46.     for(int i=0; i<n; i++){
  47.         if(a[i] == '0') sum--;
  48.         else sum++;
  49.  
  50.         //* Equal 0's and 1's 
  51.         if(first.count(sum)){
  52.             int j = first[sum];
  53.             maxLen = max(maxLen, i-j);
  54.         }
  55.  
  56.  
  57.         //* 2 extra 1's in subarray
  58.         if(first.count(sum-2)){
  59.             int j = first[sum-2];
  60.             int zr = (i-j)/2-1;
  61.             if(zeroes - zr >= 1)	maxLen = max(maxLen, i-j);
  62.         }
  63.         if(second.count(sum-2)){
  64.             int j = second[sum-2];
  65.             int zr = (i-j)/2-1;
  66.             if(zeroes - zr >= 1)	maxLen = max(maxLen, i-j);
  67.         }
  68.  
  69.  
  70.         //* 2 extra 0's in subarray
  71.         if(first.count(sum+2)){
  72.             int j = first[sum+2];
  73.  
  74.             int ons = (i-j)/2-1;
  75.             if(ones - ons >= 1)		maxLen = max(maxLen, i-j);
  76.         }
  77.         if(second.count(sum+2)){
  78.             int j = second[sum+2];
  79.  
  80.             int ons = (i-j)/2-1;
  81.             if(ones - ons >= 1)		maxLen = max(maxLen, i-j);
  82.         }
  83.  
  84.  
  85.         if(!first.count(sum)){
  86.             first[sum] = i;
  87.         }
  88.         else if(!second.count(sum)){
  89.             second[sum] = i;
  90.         }
  91.     }
  92.     return maxLen;
  93.  
  94. }
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104. int maxEqualSubarray(string a, int n){
  105.  
  106.     int ones = 0;
  107.     for(int i=0; i<n; i++) if(a[i] == '1') ones++;
  108.     int zeroes = n-ones;
  109.  
  110.     if(ones == zeroes) return n;
  111.  
  112.     unordered_map<int, int> mp = {{0, -1}};
  113.  
  114.     int sum = 0;
  115.     int maxLen = 0;
  116.  
  117.     for(int i=0; i<n; i++){
  118.         if(a[i] == '0') sum--;
  119.         else sum++;
  120.  
  121.         //* Equal 0's and 1's 
  122.         if(mp.count(sum)){
  123.             int j = mp[sum];
  124.             maxLen = max(maxLen, i-j);
  125.         }
  126.  
  127.  
  128.         //* 2 extra 1's in subarray
  129.         if(mp.count(sum-2)){
  130.             int j = mp[sum-2];
  131.             int zr = (i-j)/2-1;
  132.             if(zeroes - zr >= 1)	maxLen = max(maxLen, i-j);
  133.         }
  134.  
  135.         //* 2 extra 0's in subarray
  136.         if(mp.count(sum+2)){
  137.             int j = mp[sum+2];
  138.  
  139.             int ons = (i-j)/2-1;
  140.             if(ones - ons >= 1)		maxLen = max(maxLen, i-j);
  141.         }
  142.  
  143.         if(!mp.count(sum)){
  144.             mp[sum] = i;
  145.         }
  146.     }
  147.     return maxLen;
  148.  
  149. }
  150.  
  151.  
  152. int consistency2(int n){
  153. 	string b(a);
  154. 	reverse(begin(b), end(b));
  155.  
  156. 	return max(maxEqualSubarray(a, n) , maxEqualSubarray(b, n));
  157. }
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. int practice(int n){
  180.  
  181.  
  182.     return 0;
  183. }
  184.  
  185.  
  186.  
  187.  
  188.  
  189. void solve() {
  190.  
  191.     int n;
  192.  
  193. 	cin >> a;
  194. 	n = a.size();
  195.  
  196.     cout << consistency1(n) <<  " " << consistency2(n) << endl;
  197.  
  198.  
  199. }
  200.  
  201.  
  202.  
  203.  
  204.  
  205. int32_t main() {
  206.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  207.  
  208.     int t = 1;
  209.     cin >> t;
  210.     while (t--) {
  211.         solve();
  212.     }
  213.  
  214.     return 0;
  215. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
4
01111100
111
100001
10001010000010010
stdout
copy 
6 6
0 0
4 4
8 8
https://ideone.com/6gPzeO
language:
C++14 (gcc 8.3)
created:
7 hours 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!