Submission #68284445

---

Source Code Expand

/*
WARNING!
これはChatGPT-5の性能テストのために作成したコードです．
*/

#include <bits/stdc++.h>
using namespace std;

// ノード：正規形の長さと先頭2ビット（len==1ならaのみ有効）
struct Node {
    int len; // >=0
    unsigned char a, b; // len>=2: 先頭2ビット, len==1: a=唯一のビット, len==0: 未使用
    Node(int L=0, int A=0, int B=0): len(L), a((unsigned char)A), b((unsigned char)B) {}
};

// 3周期の配列を構成: P[0]=a, P[1]=b, P[2]=a^b^1
static inline void makeP(unsigned char a, unsigned char b, unsigned char P[3]) {
    P[0] = a & 1;
    P[1] = b & 1;
    P[2] = (P[0] ^ P[1] ^ 1) & 1;
}

// condLeft: 左末尾2要素のXOR(=P[r-2]^P[r-1]) == Q[k]
static inline bool condLeft(const unsigned char P[3], const unsigned char Q[3], int r, int k) {
    int x = P[(r+1)%3] ^ P[(r+2)%3];
    return x == Q[k];
}

// condRight: P[r-1] == Q[k]^Q[k+1]
static inline bool condRight(const unsigned char P[3], const unsigned char Q[3], int r, int k) {
    int x = P[(r+2)%3];
    int y = Q[k] ^ Q[(k+1)%3];
    return x == y;
}

// 右の容量が0のとき（=右長1）に、左だけで何回消せるかをO(1)で数える
// 固定kに対し condLeft(r,k) を r, r-1, r-2 と見て最長runを計算
static inline int additionalLeftRun(const unsigned char P[3], const unsigned char Q[3], int r, int k, int Lcap) {
    int f0 = condLeft(P,Q,r,k);
    if(!f0) return 0;
    int f1 = condLeft(P,Q,(r+2)%3,k);
    if(!f1) return min(Lcap, 1);
    int f2 = condLeft(P,Q,(r+1)%3,k);
    if(!f2) return min(Lcap, 2);
    return Lcap; // 常に消せる
}

// 左長が1（=Lcap==0）で右だけ消す場合をO(1)で数える。a=左唯一のビット。
// kは右の現在先頭の位相。
static inline int additionalRightRun_singleLeftBit(int a, const unsigned char Q[3], int k, int Rcap) {
    if(Rcap<=0) return 0;
    int r0 = (a ^ Q[k] ^ Q[(k+1)%3]);
    if(r0) return 0;
    if(Rcap==1) return 1;
    int r1 = (a ^ Q[(k+1)%3] ^ Q[(k+2)%3]);
    if(r1) return 1;
    if(Rcap==2) return 2;
    int r2 = (a ^ Q[(k+2)%3] ^ Q[k]);
    if(r2) return 2;
    // 3つとも0 → 無制限に消せる（容量の範囲で）
    return Rcap;
}

// 2ノードの結合（境界での消去を定数時間で計算）
static inline Node mergeNode(const Node& L, const Node& R) {
    if(L.len==0) return R;
    if(R.len==0) return L;

    // 右の3周期
    unsigned char Q[3];
    if(R.len>=2) {
        makeP(R.a, R.b, Q);
    } else {
        // len==1 のときも便宜上Qを作る（bはダミー）
        Q[0] = R.a & 1;
        Q[1] = 0;
        Q[2] = (Q[0]^Q[1]^1)&1;
    }

    // 左が長さ1の特別処理：右だけを前から削る
    if(L.len==1) {
        int a = L.a & 1;
        int n = R.len;
        int Rcap = max(0, n-1);
        int k = 0;
        int usedR = additionalRightRun_singleLeftBit(a, Q, k, Rcap);
        int n2 = n - usedR;
        int k2 = (k + (usedR%3)) % 3;

        int total = 1 + n2;
        if(total>=2) {
            // 先頭2つは [a, 右の先頭]
            unsigned char b = Q[k2];
            return Node(total, a, b);
        } else {
            // total==1 → a のみ
            return Node(1, a, 0);
        }
    }

    // ここから左len>=2
    unsigned char P[3];
    makeP(L.a, L.b, P);

    int m = L.len, n = R.len;
    int Lcap = m - 1;         // 左が境界削除で消せる最大回数
    int Rcap = max(0, n - 1); // 右が境界削除で消せる最大回数
    int r = m % 3;            // 左末尾の位相
    int k = 0;                // 右先頭の位相

    int usedL = 0, usedR = 0;

    // 右容量が0（右len==1）→ 左だけでO(1)
    if(Rcap == 0) {
        int t = additionalLeftRun(P, Q, r, k, Lcap);
        usedL += t;
        r = (r + 2*(t%3)) % 3;
        int m2 = m - usedL, n2 = n;
        int total = m2 + n2;
        if(total >= 2) {
            if(m2 >= 2) return Node(total, L.a, L.b);
            if(m2 == 1) return Node(total, L.a, Q[k]); // 右は位相kのまま
            // m2==0（理論上起こりにくいが一応）
            return Node(total, Q[k], Q[(k+1)%3]);
        } else {
            // total==1
            if(m2==1) return Node(1, L.a, 0);
            return Node(1, Q[k], 0);
        }
    }

    // 両側とも容量あり → まず9状態で循環検出（容量無視）
    int visited[3][3]; memset(visited, -1, sizeof(visited));
    int rr = r, kk = k;
    vector<pair<int,int>> st; st.reserve(16);
    vector<int> ops; ops.reserve(16); // 0=L, 1=R
    st.emplace_back(rr,kk);
    while (true) {
        if (visited[rr][kk] != -1) {
            // 既出 → cycle
            int start = visited[rr][kk];
            // pre: [0, start), cycle: [start, ops.size())
            break;
        }
        visited[rr][kk] = (int)ops.size();
        bool Lok = condLeft(P,Q,rr,kk);
        bool Rok = condRight(P,Q,rr,kk);
        if(!Lok && !Rok) {
            // 終端（cycle長0）
            break;
        }
        int op = Lok ? 0 : 1;
        ops.push_back(op);
        if(op==0) rr = (rr+2)%3;
        else      kk = (kk+1)%3;
        st.emplace_back(rr,kk);
    }
    int cycle_start = visited[rr][kk]==-1 ? (int)ops.size() : visited[rr][kk];
    int pre_len = cycle_start;
    int cyc_len = (int)ops.size() - cycle_start;

    // 容量を考慮して実際に進める
    rr = r; kk = k;
    // まず前周期（高々9ステップ）
    int i = 0;
    for (; i < pre_len; ++i) {
        bool Lok = condLeft(P,Q,rr,kk);
        bool Rok = condRight(P,Q,rr,kk);
        if (Lok && Lcap>0) {
            --Lcap; ++usedL; rr = (rr+2)%3;
        } else if (Rok && Rcap>0) {
            --Rcap; ++usedR; kk = (kk+1)%3;
        } else {
            break;
        }
    }
    if (i < pre_len) {
        // ここで停止（容量枯渇 or どちらも不可）
        if (Rcap==0) {
            int t = additionalLeftRun(P, Q, rr, kk, Lcap);
            usedL += t; rr = (rr + 2*(t%3)) % 3;
        } else if (Lcap==0) {
            int t = additionalRightRun_singleLeftBit(L.a, Q, kk, Rcap);
            usedR += t; kk = (kk + (t%3)) % 3;
        }
    } else {
        // 前周期を全部消化
        if (cyc_len == 0) {
            // もう終端
        } else {
            // 循環1回分の左右回数を数える
            int cL=0, cR=0;
            for (int j=cycle_start;j<(int)ops.size();++j) (ops[j]==0?cL:cR)++;
            if (cL==0 && cR==0) {
                // ありえないが安全策
            } else if (cL==0) {
                // 右だけ無限に消せる（容量の範囲で）
                int take = Rcap; usedR += take; Rcap = 0; kk = (kk + (take%3)) % 3;
                // 右が尽きたら左だけ追加で消せる可能性
                if (Lcap>0) {
                    int t = additionalLeftRun(P, Q, rr, kk, Lcap);
                    usedL += t; rr = (rr + 2*(t%3)) % 3;
                }
            } else if (cR==0) {
                // 左だけ無限に
                int take = Lcap; usedL += take; Lcap = 0; rr = (rr + 2*(take%3)) % 3;
                if (Rcap>0) {
                    int t = additionalRightRun_singleLeftBit(L.a, Q, kk, Rcap);
                    usedR += t; kk = (kk + (t%3)) % 3;
                }
            } else {
                // 両方ある → 周期をまとめて消費
                int tmaxL = Lcap / cL;
                int tmaxR = Rcap / cR;
                int tapply = min(tmaxL, tmaxR);
                if (tapply > 0) {
                    usedL += tapply * cL; Lcap -= tapply * cL;
                    usedR += tapply * cR; Rcap -= tapply * cR;
                    rr = (rr + 2*((tapply*cL)%3)) % 3;
                    kk = (kk + ((tapply*cR)%3)) % 3;
                }
                // 余り（<=周期長）を1手ずつ
                for (int step=0; step<cyc_len; ++step) {
                    bool Lok = condLeft(P,Q,rr,kk);
                    bool Rok = condRight(P,Q,rr,kk);
                    if (Lok && Lcap>0) {
                        --Lcap; ++usedL; rr = (rr+2)%3;
                    } else if (Rok && Rcap>0) {
                        --Rcap; ++usedR; kk = (kk+1)%3;
                    } else {
                        break;
                    }
                }
                // 一方が尽きたら片側追加分
                if (Rcap==0) {
                    int t = additionalLeftRun(P, Q, rr, kk, Lcap);
                    usedL += t; rr = (rr + 2*(t%3)) % 3;
                } else if (Lcap==0) {
                    int t = additionalRightRun_singleLeftBit(L.a, Q, kk, Rcap);
                    usedR += t; kk = (kk + (t%3)) % 3;
                }
            }
        }
    }

    int m2 = m - usedL, n2 = n - usedR;
    int total = m2 + n2;

    if (total >= 2) {
        if (m2 >= 2) return Node(total, L.a, L.b);
        if (m2 == 1) return Node(total, L.a, Q[kk]);
        return Node(total, Q[kk], Q[(kk+1)%3]);
    } else {
        if (m2==1) return Node(1, L.a, 0);
        return Node(1, Q[kk], 0);
    }
}

// ---- セグ木 ----
struct SegTree {
    int n;
    vector<Node> seg;
    SegTree(int N=0): n(1) {
        while(n < N) n <<= 1;
        seg.assign(2*n, Node());
    }
    void build(const vector<int>& A) {
        int N = (int)A.size()-1; // 1-indexed
        for (int i=1;i<=N;i++) seg[n+i-1] = Node(1, A[i]&1, 0);
        for (int i=n+N;i<2*n;i++) seg[i] = Node(0,0,0);
        for (int i=n-1;i>=1;i--) seg[i] = mergeNode(seg[i<<1], seg[i<<1|1]);
    }
    void point_flip(int idx) {
        int p = n + idx - 1;
        int v = seg[p].len ? (seg[p].a^1) : 1; // lenは1のはず
        seg[p] = Node(1, v, 0);
        for (p >>= 1; p >= 1; p >>= 1) {
            seg[p] = mergeNode(seg[p<<1], seg[p<<1|1]);
        }
    }
    int answer_len() const { return seg[1].len; }
};

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

    int N;
    if(!(cin>>N)) return 0;

    vector<int> A(N+1);
    // A の読み取り：文字列 or 整数列の両対応
    {
        // 次のトークンを覗く
        string s; cin >> s;
        bool ok = ((int)s.size()==N);
        if (ok) {
            for(char c: s) if(c!='0' && c!='1'){ ok=false; break; }
        }
        if (ok) {
            for (int i=1;i<=N;i++) A[i] = (s[i-1]-'0')&1;
        } else {
            // s を数として扱い直す
            A[1] = stoi(s) & 1;
            for (int i=2;i<=N;i++) { int x; cin>>x; A[i]=x&1; }
        }
    }

    SegTree st(N);
    st.build(A);

    int Q;
    cin >> Q;
    while(Q--){
        int i; cin >> i;
        A[i] ^= 1;
        st.point_flip(i);
        cout << st.answer_len() << '\n';
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘Node mergeNode(const Node&, const Node&)’:
Main.cpp:141:17: warning: unused variable ‘start’ [-Wunused-variable]
  141 |             int start = visited[rr][kk];
      |                 ^~~~~

Judge Result