fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. // GCC Optimizations
  6. #pragma GCC diagnostic ignored "-Wunused-variable" // Ignore unused variable warning
  7. #pragma GCC diagnostic ignored "-Wunknown-pragmas" // Ignore unknown pragmas warning
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  10. #pragma GCC optimize("unroll-loops")
  11.  
  12. // Macros
  13. #define int long long
  14. #define ll long long
  15. #define ld long double
  16.  
  17. // Constants
  18. constexpr long long SZ = 1e5 + 7;
  19. constexpr long long inf = 1e18;
  20. constexpr long long mod = 1e9 + 7;
  21. constexpr long long MOD = 998244353;
  22. constexpr long double PI = 3.141592653589793238462;
  23.  
  24. // Macros
  25. #define vt vector // not cool
  26. #define pb push_back
  27. #define all(X) (X).begin(), (X).end()
  28. #define allr(X) (X).rbegin(), (X).rend()
  29. #define sz(X) (int)X.size()
  30.  
  31. #define each(x, a) for (auto &x: a)
  32. #define forn(i, n) for (int i = 0; i < n; ++i)
  33. #define forr(i, n) for (int i = n; i >=0; --i)
  34.  
  35. #define fi first
  36. #define se second
  37. #define endl '\n'
  38.  
  39. #define setbits(X) __builtin_popcountll(X)
  40. #define fix(X) fixed << setprecision(X)
  41. #define mem0(X) memset((X), 0, sizeof((X)))
  42. #define mem1(X) memset((X), -1, sizeof((X)))
  43.  
  44. // Debug Functions
  45. void __print(int x) { cerr << x; }
  46. void __print(unsigned long long x) { cerr << x; }
  47. void __print(long double x) { cerr << x; }
  48. void __print(char x) { cerr << x; }
  49. void __print(const char *x) { cerr << x; }
  50. void __print(const string &x) { cerr << x; }
  51. void __print(bool x) { cerr << (x ? "true" : "false"); }
  52. template<typename T, typename V>
  53. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
  54. template<typename T>
  55. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) {cerr << (f++ ? ", " : ""); __print(i);} cerr << "}";}
  56. void _print() {cerr << "]\n";}
  57. template<typename T, typename... V>
  58. void _print(T t, V... v) {__print(t); if (sizeof...(v)) {cerr << ", ";} _print(v...);}
  59.  
  60. #ifdef ambarsariya
  61. #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
  62. #else
  63. #define  dbg(x...)
  64. #endif
  65.  
  66. // Min Max
  67. template<class T>
  68. bool amin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
  69. template<class T>
  70. bool amax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
  71.  
  72. // Operator overloads <<, >>
  73. template<typename T1, typename T2> // cin >> pair
  74. istream &operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
  75. template<typename T> // cin >> vector
  76. istream &operator>>(istream &istream, vector<T> &v) { for (auto &it : v) { cin >> it; } return istream; }
  77. template<typename T1, typename T2> // cout << pair
  78. ostream &operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
  79. template<typename T> // cout << vector
  80. ostream &operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) { cout << it << " "; } return ostream; }
  81.  
  82. // Google
  83. int tc_cnt = 1;
  84. #define ns()               cout << "Case #" << tc_cnt ++ << ": ";
  85.  
  86. // Power under mod (a ^ b) % mod
  87. int modpow(int a, int b, int m = mod) {
  88.     a = a & m; int ans = 1;
  89.     while (b) {
  90.         if (b & 1) { ans = (ans * a) % m; }
  91.         b = b >> 1; a = (a * a) % m;
  92.     }
  93.     return ans;
  94. }
  95.  
  96. // Inverse Mod (1 / a) % mod
  97. int modinv(int a, int m = mod) { return modpow(a, m - 2); }
  98.  
  99. // Modular Arithematic
  100. int modadd(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
  101. int modsub(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
  102. int modmul(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
  103. int moddiv(int a, int b, int m = mod) { a = a % m; b = b % m; return (modmul(a, modinv(b, m), m) + m) % m; }
  104.  
  105. // GCD
  106. int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }
  107.  
  108. // LCM
  109. int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
  110.  
  111. // Directions
  112. const int dx[8] = {0, 1, -1, 0, -1, -1, 1, 1};
  113. const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
  114.  
  115. int mul(int a, int b) {
  116.     int ans = 0;
  117.     while (b) {
  118.         if (b & 1) {
  119.             ans += a;
  120.         }
  121.         b = b >> 1;
  122.         a += a;
  123.         if (a > inf) {
  124.             a = inf;
  125.         }
  126.         if (ans > inf) {
  127.             ans = inf;
  128.         }
  129.     }
  130.     return ans;
  131. }
  132.  
  133. bool cmp(pair<int,int> a,pair<int,int> b){
  134.     if(a.first==b.first){
  135.         return a.second<b.second;
  136.     }
  137.     return a.first<b.first;
  138. }
  139. vector<int> cnt;
  140. class Compare
  141. {
  142. public:
  143.     bool operator() (pair<int,int> a, pair<int,int> b)
  144.     {
  145.         if(a.first==b.first){
  146.             return cnt[a.second]>cnt[b.second];
  147.         }
  148.         return a.first>b.first;
  149.     }
  150. };
  151. // solution
  152. void solve(){
  153. 	// taking in the input
  154.     string s;
  155.     cin>>s;
  156.     cnt.clear();
  157.     string s1="";
  158.     int count=0;
  159.     // here i am counting the number of zeros and pushing it into the array as it is better to remove all the contnous zeros than
  160.     // removing only one zero
  161.     for(int i=0;i<s.length();i++){
  162.         if(s[i]=='0'){
  163.             count++;
  164.         }
  165.         else{
  166.             if(count>0)cnt.push_back(count);
  167.             count=0;
  168.         }
  169.  
  170.     }
  171.     if(count>0)cnt.push_back(count);
  172.     // here im storing the number of zeros in count variable
  173.     count=accumulate(cnt.begin(),cnt.end(),(ll)0);
  174.     int n=s.length();
  175.     // here i am compressing the string to remove consequent zeros and replacing it with only 1 zero
  176.     for(int i=0;i<n;){
  177.         if(s[i]=='1'){
  178.             s1+='1';
  179.             i++;
  180.         }
  181.         else{
  182.             s1+='0';
  183.             while(i<n and s[i]=='0')i++;
  184.         }
  185.     }
  186.     s=s1;
  187.     n=s.length();
  188.     int cz=0;
  189.     int c=0;
  190.     // here basically im taking a priority queue and adding in it how many ones to get to this zero by going from left and right and storing the min in it
  191.     priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>> > q;
  192.     vector<int> v;
  193.     for(int i=0;i<n;i++){
  194.         if(s[i]=='0'){
  195.             v.push_back(c);
  196.             cz++;
  197.             c=0;
  198.         }
  199.         else{
  200.             c++;
  201.         }
  202.     }
  203.     c=0;
  204.     int z=0;
  205.     for(int i=n-1;i>=0;i--){
  206.         if(s[i]=='0'){
  207.             z++;
  208.             v[cz-z]=min(v[cz-z],c);
  209.             c=0;
  210.             q.push({v[cz-z],cz-z});
  211.         }
  212.         else{
  213.             c++;
  214.         }
  215.     }
  216.     // the worst ans is the number of zeros present
  217.     int ans=count;
  218.     // sum is to count the number of ones removes
  219.     int sum=0;
  220.     // while q is not empty
  221.     while(!q.empty()){
  222.     	// removing the min ones
  223.         sum+= (q.top().first);
  224.         // removing the zeros after this ones
  225.         count-=cnt[q.top().second];
  226.         q.pop();
  227.         // calculating the ans
  228.         ans=min({ans,max(sum,count)});
  229.     }
  230.     cout<<ans<<endl;
  231.  
  232. }
  233.  
  234. int32_t main() {
  235.     ios_base::sync_with_stdio(false);
  236.     cin.tie(0);
  237.     cout.tie(0);
  238.     int t = 1;
  239.     cin >> t;
  240.     while (t--) solve();
  241.     return 0;
  242. }
Success #stdin #stdout 0.01s 5404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/bBoj0b
language:
C++ (gcc 8.3)
created:
2 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!