fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int n;
  10.     cin >> n;
  11.     string s;
  12.     cin >> s;
  13.  
  14.     // Count winning substrings that are entirely '0' (length >= 2).
  15.     long long ans = 0;
  16.     long long cnt = 0;
  17.     for (int i = 0; i < n; i++){
  18.         if (s[i] == '0')
  19.             cnt++;
  20.         else {
  21.             if (cnt > 0){
  22.                 ans += cnt * (cnt - 1LL) / 2; // Each maximal block of zeros contributes L*(L-1)/2.
  23.                 cnt = 0;
  24.             }
  25.         }
  26.     }
  27.     if (cnt > 0)
  28.         ans += cnt * (cnt - 1LL) / 2;
  29.  
  30.     // Count substrings of length 3 that are winning due to circular adjacency.
  31.     // These substrings have exactly two zeros (so that even if they aren't consecutive linearly,
  32.     // the zeros are adjacent in the circular view).
  33.     for (int i = 0; i <= n - 3; i++){
  34.         int zeros = 0;
  35.         zeros += (s[i] == '0');
  36.         zeros += (s[i+1] == '0');
  37.         zeros += (s[i+2] == '0');
  38.         if (zeros == 2)
  39.             ans++;
  40.     }
  41.  
  42.     cout << ans << "\n";
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10
0010010011
stdout
copy 
10
https://ideone.com/lFi5gj
language:
C++ (gcc 8.3)
created:
10 days 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!