結果

問題 No.3120 Lower Nim
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-24 14:48:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,661 bytes
コンパイル時間 2,246 ms
コンパイル使用メモリ 195,776 KB
実行使用メモリ 26,224 KB
平均クエリ数 2233.55
最終ジャッジ日時 2025-04-24 14:48:48
合計ジャッジ時間 10,228 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    // 初期の K は ∑A_i ≤ 10000 より大きければ十分
    int K = 10001;

    // 山の XOR を計算するラムダ
    auto calcXor = [&](){
        int x = 0;
        for(int v : A) x ^= v;
        return x;
    };

    // 初期 XOR で先手・後手を決定
    int S = calcXor();
    bool isFirst = (S != 0);

    if(isFirst){
        cout << "First\n" << flush;
    } else {
        cout << "Second\n" << flush;
    }

    bool ourTurn = isFirst;
    while(true){
        int ret, i, x;

        if(!ourTurn){
            // ジャッジ（相手）の手番結果を読み込む
            cin >> i >> x;
            cin >> ret;
            if(ret == -1){
                // 我々の敗北
                return 0;
            }
            // 継続なら更新
            --i;
            A[i] -= x;
            K = x;
        }

        // 我々の手番
        S = calcXor();
        int move_i = -1, move_x = 1;

        if(S != 0){
            // XOR を 0 に戻せる取りを探す
            for(int j = 0; j < N; j++){
                int a = A[j];
                int t = a ^ S;
                if(t < a){
                    int r = a - t;
                    if(r <= K){
                        move_i = j;
                        move_x = r;
                        break;
                    }
                }
            }
        }

        if(move_i == -1){
            // XOR=0 か、制限 K の下で XOR=0 にできない場合
            // まず可能なら K 個取って制限を変えずに維持
            for(int j = 0; j < N; j++){
                if(A[j] >= K){
                    move_i = j;
                    move_x = K;
                    break;
                }
            }
            // それもできなければ 1 個だけ取る
            if(move_i == -1){
                for(int j = 0; j < N; j++){
                    if(A[j] > 0){
                        move_i = j;
                        move_x = 1;
                        break;
                    }
                }
            }
        }

        // 手を出力
        A[move_i] -= move_x;
        cout << (move_i + 1) << " " << move_x << "\n" << flush;

        // 判定を読み込む
        cin >> ret;
        // ret=1: 勝利, ret=0: 継続, ret=-1: 敗北
        if(ret != 0){
            return 0;
        }
        K = move_x;
        ourTurn = false;
    }
    return 0;
}
0