提出 #68376172

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF = (1ll << 60);
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}

pair<ll, ll> f(string S, int v){
    array<int, 4> a;
    {
        int tmp = v;
        rep(i, 0, 4){
            a[3 - i] = (tmp & 1);
            tmp /= 2;
        }
    }
    auto g = [&](int ind) -> int {
        return a[(S[ind] - '0') * 2 + S[ind + 1] - '0'];
    };
    ll N = S.size();
    if (N == 1){
        if (S == "1"){
            return {1, 1};
        }
        return {-1, 0};
    }
    if (a[1] == 1 && a[2] == 0){
        reverse(S.begin(), S.end());
        return f(S, v - 2);
    }
    ll L = -1, M = 0;
    auto lower_2 = [&]() -> void {
        rep(i, 0, N) if (S[i] == '1') L = 1, M++;
        rep(i, 0, N - 1) if (g(i)) L = 2, M++;
    };
    if (N == 2){
        lower_2();
        return {L, M};
    }
    // 0
    if (v == 0){
        rep(i, 0, N) if (S[i] == '1') L = 1, M++;
        return {L, M};
    }
    // 1
    // 1 のみ
    if (v == 1){
        for (ll l = 0, r = 0; l < N; l = r + 1, r = l){
            while (r != N && S[r] == '1') r++;
            if (r - l){
                chmax(L, r - l);
                M += (r - l) * (r - l + 1) / 2;
            }
        }
        return {L, M};
    }
    // 2 (4)
    // 1 から始まる
    // 1100000... 以外
    if (v == 2){
        lower_2();
        rep(i, 0, N - 2){
            if (S[i] == '1'){
                if (S[i + 1] == '0') {
                    chmax(L, N - i);
                    M += N - 2 - i;
                }
                else{
                    int tmp = i + 2;
                    while (tmp != N && S[tmp] == '0') tmp++;
                    if (tmp != N){
                        M += N - tmp;
                        chmax(L, N - i);
                    }
                }
            }
        }
        return {L, M};
    }
    // 3. 5
    // 左が 1
    if (v == 3){
        rep(i, 0, N){
            if (S[i] == '1'){
                chmax(L, (ll)(N - i));
                M += N - i;
            }
        }
        return {L, M};
    }
    // 6
    // 1 がきすー
    if (v == 6){
        ll A = 1, X = 0;
        ll B = 0, Y = INF;
        rep(i, 0, N){
            if (S[i] == '1'){
                swap(A, B);
                swap(X, Y);
            }
            M += B;
            chmax(L, i + 1 - Y);
            A++;
            chmin(X, i + 1ll);
        }
        return {L, M};
    }
    // 7
    // all 0 でない
    // or
    if (v == 7){
        for (auto &c : S) c = (c == '1' ? '0' : '1');
        auto [l, m] = f(S, 1);
        M = N * (N + 1) / 2 - m;
        L = N;
        if (M == 0) L = -1;
        return {L, M};
    }
    // 8
    if (v == 8){
        rep(ran, 1, N + 1){
            if (ran >= 4){
                chmax(L, (ll)ran);
                M += N + 1 - ran;
                continue;
            }
            rep(i, 0, N - ran + 1){
                vector dp(2, vector(ran, vector<bool>(ran + 1)));
                rep(j, 0, ran) dp[S[i + j] - '0'][j][j + 1] = true;
                for (int l = ran - 1; l >= 0; l--) rep(r, l + 1, ran + 1){
                    rep(k, l + 1, r) rep(x, 0, 2) rep(y, 0, 2){
                        if (dp[x][l][k] && dp[y][k][r]){
                            dp[1 - (x | y)][l][r] = true;
                        }
                    }
                }
                if (dp[1][0][ran]) L = ran, M++;
            }
        }
        return {L, M};
    }
    // 9
    // 0 がぐースー
    if (v == 9){
        ll A = 1, X = 0;
        ll B = 0, Y = INF;
        rep(i, 0, N){
            if (S[i] == '0'){
                swap(A, B);
                swap(X, Y);
            }
            M += A;
            chmax(L, i + 1 - X);
            A++;
            chmin(X, i + 1ll);
        }
        return {L, M};
    }
    // 10
    if (v == 10){
        lower_2();
        M += N * (N + 1) / 2 - N - (N - 1);
        L = N;
        return {L, M};
    }
    if (v == 11){
        // L のチェック
        {
            L = N - 1;
            if (S[0] == '1') L = N;
            rep(i, 1, N) if (S[i] == '0') L = N;
        }
        M += N * (N + 1) / 2;
        for (int l = 0, r = 0; l < N; l = r){
            if (S[l] == '1'){
                r++;
                continue;
            }
            r++;
            while (r < N && S[r] == '1') r++;
            M -= r - l;
        }
        return {L, M};
    }
    if (v == 14){
        lower_2();
        if (S != "101") L = N;
        M += N * (N + 1) / 2 - N - (N - 1);
        rep(i, 0, N - 2) if (S.substr(i, 3) == "101") M--;
        return {L, M};
    }
    if (v == 15){
        lower_2();
        L = N;
        M += N * (N + 1) / 2 - N - (N - 1);
        return {L, M};
    }
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S;
    cin >> S;
    rep(i, 0, 16){
        auto [L, M] = f(S, i);
        cout << L << " " << M << "\n";
    }
}

提出情報

ジャッジ結果