結果

問題 No.3140 Weird Parentheses Game
コンテスト
ユーザー nhtloc
提出日時 2025-11-28 11:48:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,465 bytes
コンパイル時間 1,891 ms
コンパイル使用メモリ 201,532 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-28 11:48:29
合計ジャッジ時間 3,016 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// Compute Grundy numbers for bracket game
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    vector<int> grundy(N, 0);
    stack<int> st;

    for (int i = 0; i < N; i++) {
        if (S[i] == '(') {
            st.push(i);
        } else {
            int l = st.top();
            st.pop();

            // XOR tất cả grundy trong phạm vi (l, i)
            int g = 0;
            int j = l + 1;
            while (j < i) {
                g ^= grundy[j];
                // bỏ qua toàn bộ khối con
                int depth = 1;
                int k = j + 1;
                while (k < i && depth > 0) {
                    if (S[k] == '(') depth++;
                    else depth--;
                    k++;
                }
                j = k;
            }
            grundy[l] = 1 ^ g;
            grundy[i] = grundy[l];
        }
    }

    // XOR tất cả grundy của các khối gốc
    int nim_sum = 0;
    int i = 0;
    while (i < N) {
        if (S[i] == '(') {
            nim_sum ^= grundy[i];
            int depth = 1;
            int j = i + 1;
            while (j < N && depth > 0) {
                if (S[j] == '(') depth++;
                else depth--;
                j++;
            }
            i = j;
        } else i++;
    }

    cout << (nim_sum ? "First" : "Second") << "\n";
    return 0;
}
0