Submission #3013195


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

string s;

int dp[303030];

int rec2(int idx) {
  if(idx == s.size()) return 1;
  if(~dp[idx]) return dp[idx];
  int ret = 0;
  for(int i = 0; i < 2; i++) {
    if((s[idx] >> i) & 1) ret += rec2(idx + 1);
  }
  return dp[idx] = ret % mod;
}

int dp2[303030][3][3];

int rec1(int idx, int prefix, int prefixsz) {
  if(idx >= s.size()) return prefixsz == 1 && prefix == 1;
  if(~dp2[idx][prefix][prefixsz]) return dp2[idx][prefix][prefixsz];
  if(idx + 1 == s.size()) {
    if(prefixsz == 1) return false;
    return (s[idx] & 2) != 0;
  }
  int64 ret = 0;
  if(prefixsz == 0) {
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j < 2; j++) {
        int k = (i << 1) | j;
        if((s[idx] >> i) & 1 && (s[idx + 1] >> j) & 1) {
          if(k == 0b00 && idx + 2 < s.size()) {
            for(int l = 0; l < 2; l++) if((s[idx + 2] >> l) & 1) ret += rec1(idx + 3, 0, 1);
          }
          if(k == 0b01) ret += rec1(idx + 2, 0, 0);
          if(k == 0b11) ret += rec2(idx + 2);
          if(k == 0b10 && idx + 2 < s.size()) {
            for(int l = 0; l < 2; l++) {
              if((s[idx + 2] >> l) & 1) {
                if(l == 0) {
                  if(idx + 3 < s.size()) {
                    for(int p = 0; p < 2; p++) {
                      if((s[idx + 3] >> p) & 1) ret += rec1(idx + 4, 2, 2);
                    }
                  }
                }
                if(l == 1) ret += rec1(idx + 3, 1, 1);
              }
            }
          }
        }
      }
    }
  } else if(prefixsz == 1) {
    for(int j = 0; j < 2; j++) {
      int k = (prefix << 1) | j;
      if((s[idx] >> j) & 1) {
        if(k == 0b00 && idx + 1 < s.size()) {
          for(int l = 0; l < 2; l++) if((s[idx + 1] >> l) & 1) ret += rec1(idx + 2, 0, 1);
        }
        if(k == 0b01) ret += rec1(idx + 1, 0, 0);
        if(k == 0b11) ret += rec2(idx + 1);
        if(k == 0b10 && idx + 1 < s.size()) {
          for(int l = 0; l < 2; l++) {
            if((s[idx + 1] >> l) & 1) {
              if(l == 0) {
                if(idx + 2 < s.size()) {
                  for(int p = 0; p < 2; p++) {
                    if((s[idx + 2] >> p) & 1) ret += rec1(idx + 3, 2, 2);
                  }
                }
              }
              if(l == 1) ret += rec1(idx + 2, 1, 1);
            }
          }
        }
      }
    }
  } else {
    for(int l = 0; l < 2; l++) {
      if((s[idx] >> l) & 1) {
        if(l == 0) {
          if(idx + 1 < s.size()) {
            for(int p = 0; p < 2; p++) {
              if((s[idx + 1] >> p) & 1) ret += rec1(idx + 2, 2, 2);
            }
          }
        }
        if(l == 1) ret += rec1(idx + 1, 1, 1);
      }
    }
  }
  return dp2[idx][prefix][prefixsz] = ret % mod;
}


int main() {
  cin >> s;
  for(auto &c : s) {
    if(c == '1') c = 2;
    else if(c == '0') c = 1;
    else c = 3;
  }
  memset(dp, -1, sizeof(dp));
  memset(dp2, -1, sizeof(dp2));
  cout << rec1(0, 0, 0) << endl;
}

Submission Info

Submission Time
Task E - Median Replace
User ei13333
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 3148 Byte
Status
Exec Time 45 ms
Memory 31236 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 1600 / 1600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 5 ms 12032 KB
02.txt 5 ms 12032 KB
03.txt 6 ms 12032 KB
04.txt 5 ms 12032 KB
05.txt 5 ms 12032 KB
06.txt 18 ms 18048 KB
07.txt 45 ms 31236 KB
08.txt 11 ms 15232 KB
09.txt 35 ms 28932 KB
10.txt 24 ms 23172 KB
11.txt 36 ms 28932 KB
12.txt 21 ms 22532 KB
13.txt 35 ms 31236 KB
14.txt 6 ms 12288 KB
15.txt 33 ms 31236 KB
16.txt 19 ms 19716 KB
17.txt 35 ms 28932 KB
18.txt 21 ms 21508 KB
19.txt 32 ms 28932 KB
20.txt 9 ms 14080 KB
21.txt 41 ms 31236 KB
22.txt 28 ms 25220 KB
23.txt 39 ms 31236 KB
24.txt 13 ms 16384 KB
25.txt 37 ms 30084 KB
26.txt 16 ms 18176 KB
27.txt 35 ms 31236 KB
28.txt 15 ms 18048 KB
29.txt 44 ms 31236 KB
30.txt 30 ms 28420 KB
31.txt 40 ms 31236 KB
32.txt 24 ms 22532 KB
33.txt 38 ms 31236 KB
34.txt 19 ms 22404 KB
35.txt 32 ms 31236 KB
36.txt 27 ms 23940 KB
37.txt 40 ms 31236 KB
38.txt 27 ms 23812 KB
39.txt 42 ms 31236 KB
40.txt 11 ms 15104 KB
41.txt 42 ms 31236 KB
42.txt 12 ms 17792 KB
43.txt 27 ms 31236 KB
s1.txt 5 ms 12032 KB
s2.txt 5 ms 12032 KB
s3.txt 5 ms 12032 KB