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