Artifact fd2a8960b68fd4511d241f229590c8975bf41044
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class BalancedSubstrings { public:
int countSubstrings(string s)
{
const int N = s.size();
int numAllZeroRange = 0;
for(int i=0; i<N; ++i)
for(int k=i; k<N && s[k]=='0'; ++k)
++numAllZeroRange;
vector<int> leftZero(N), rightZero(N);
for(int i=1; i<N; ++i)
leftZero[i] = (s[i-1]=='0' ? leftZero[i-1]+1 : 0);
for(int i=N-2; i>=0; --i)
rightZero[i] = (s[i+1]=='0' ? rightZero[i+1]+1 : 0);
set<pair<int,int>> OneOneRange;
for(int c=0; c<N; ++c) {
// take c as the center.
// enumerate all balanced [L, R].
int L=c, R=c, Lw=0, Rw=0;
if(s[L]=='1')
OneOneRange.emplace(L,R);
while(0<=L && R<N) {
const bool moveL = (Lw<Rw || Lw==Rw);
const bool moveR = (Lw>Rw || Lw==Rw);
if(moveL)
while(--L>=0)
if(s[L]=='1') {
Lw += (c-L);
break;
}
if(moveR)
while(++R<N)
if(s[R]=='1') {
Rw += (R-c);
break;
}
if(0<=L && R<N && Lw==Rw)
OneOneRange.emplace(L, R);
}
}
int numOtherRange = 0;
for(auto lr: OneOneRange) {
int L = lr.first, R = lr.second;
numOtherRange += (leftZero[L]+1) * (rightZero[R]+1);
}
return numAllZeroRange + numOtherRange;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, BalancedSubstrings().countSubstrings(s));}
int main(){
CASE(0)
string s = "011";
int _ = 4;
END
CASE(1)
string s = "10111";
int _ = 10;
END
CASE(2)
string s = "00000";
int _ = 15;
END
CASE(3)
string s = "0000001000000";
int _ = 91;
END
CASE(4)
string s = "100110001001";
int _ = 49;
END
CASE(5)
string s = "0";
int _ = 1;
END
CASE(5)
string s = "1";
int _ = 1;
END
CASE(5)
string s = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
int _ = 1563750;
END
CASE(5)
string s = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
int _ = 3126250;
END
CASE(5)
string s = "1000111010010001011011011010000101101001011001001010101001010100101011011101011111101011011111110001001110010101111010101000001011100011100110101011010001010010110001000111000010110101111101100001000010100010000000101101010011100000000010100010011000101010100100111101001000000000001111011001011101010000011000000110011111011110100101011011111101001111000101011000101110101001001000001101100101000110100111000110100000000011001110110110011011110101101010111010011011101101111110010110101100001101111111101010000010001001001001110111001101110000111001110101111000110011010101010111100001001111110010101010100000010011111010100001101100111111010110010110011010101110110100001100000111000011100100000110111101110010101011101101101100001100111111110011100101101111000011010001000111011001100010100110001010101011101110100100101001000000010000001000001111001110111101110011000111010010101110000111101011010000011000101111011000101110101000011000110010011011001000001001111100110001011110010101000000001110010111100101101111100000001110000011100101001000100011101100011010010100011101111100001010111101000110010111000110101000101100001101111111011000111001110010011010011111100101000000010101110100100101100010001000101001110100001111010100011110000010001011100000100110010111000111110010101110000000110010000111001000010010111011111110110100000101011110000100110101111000111010001001101100000111010101000000011110001101011001010010101001111111010101001011010010011110111110100011000100111010010101111101011010001110001111011000101110101001110111000010100101110001110011110111101111000011100111010100011010100110110010100001100000000000110100001101110001001100011001111001001101011000110011101100010110011001100100111110010011001101111110000011010111111100101000110001111101101011111001011000010101111000110100000000111100100100001010011001100001101010100001101010101100110001100110110111111101000101000000101111010010010101000011101100100010100000111111101001010100000110110110110011110111010010100001100001010001000001000001111001001111110001100010001001101101110110111010011010100101101010111000010100001000000010010010110110110000010100010010101111101101001111101001010000011000010000011000011111010001101101101011100001101010001001011001011000010100101010000111010101111100101010111111111100010111101101110110101110101110100010010010011101010001010011110111010111011010011110111000100111000111100001111011001010010111010101001000110010000010110001011111111000001100001000100001000111000111111011110101";
int _ = 36497;
END
}
// END CUT HERE