結果

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

ソースコード

diff #
raw source code 

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

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

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

    vector<int> dp(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 đoạn (l, i)
            int g = 0;
            int j = l + 1;
            while (j < i) {
                g ^= dp[j];
                // bỏ qua khối ngoặc con
                int depth = 1, k = j + 1;
                while (k < i && depth > 0) {
                    if (S[k] == '(') depth++;
                    else depth--;
                    k++;
                }
                j = k;
            }
            dp[l] = g + 1;
            dp[i] = dp[l];
        }
    }

    int nim_sum = 0;
    int i = 0;
    while (i < N) {
        if (S[i] == '(') {
            nim_sum ^= dp[i];
            int depth = 1, 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";
}
0