fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define fi first
  5. #define se second
  6. typedef long double ld;
  7. int main()
  8. {
  9.     int tt = 1;
  10.     cin >> tt;
  11.     while (tt--)
  12.     {
  13.         string a;
  14.         cin >> a;
  15.         ll n = a.length();
  16.         int left = 0, right = n;
  17.         vector<int> s(n + 1, 0);
  18.         vector<int> p(n + 1, 0);
  19.         for (int i = n - 1; i >= 0; i--)
  20.         {
  21.             s[i] = s[i + 1];
  22.             if (a[i] == '1')
  23.                 ++s[i];
  24.         }
  25.         for (int i = 0; i < n; i++)
  26.         {
  27.             p[i + 1] = p[i];
  28.             if (a[i] == '0')
  29.                 ++p[i + 1];
  30.         }
  31.         int ans = INT_MAX;
  32.         while (left <= right)
  33.         {
  34.             int mid = left + right;
  35.             mid /= 2;
  36.             int cnt = 0;
  37.             int cnt1 = 0;
  38.             for (int i = 0; i < n; i++)
  39.             {
  40.                 ll l = i, r = n - 1, id1 = -1;
  41.                 while (l <= r)
  42.                 {
  43.                     ll m = l + r;
  44.                     m /= 2;
  45.                     if (p[m + 1] - p[i] <= mid)
  46.                         l = m + 1, id1 = m;
  47.                     else
  48.                         r = m - 1;
  49.                 }
  50.                 if (id1 != -1)
  51.                 {
  52.                     int h = cnt + s[id1 + 1];
  53.                     if (h <= mid)
  54.                     {
  55.                         ++cnt1;
  56.                     }
  57.                 }
  58.                 if (a[i] == '1')
  59.                 {
  60.                     cnt += 1;
  61.                 }
  62.             }
  63.             if (cnt <= mid)
  64.                 ++cnt1;
  65.             if (cnt1)
  66.             {
  67.                 ans = mid;
  68.                 right = mid - 1;
  69.             }
  70.             else
  71.                 left = mid + 1;
  72.         }
  73.         cout << ans << "\n";
  74.     }
  75. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/jdqt0c
language:
C++14 (gcc 8.3)
created:
2 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!