結果

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

ソースコード

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 なので、それより大きければ OK)
    int K = 10001;

    // 現在の山の XOR
    auto calcXor = [&](){
        int x = 0;
        for(int v: A) x ^= v;
        return x;
    };

    int S = calcXor();
    bool isFirst = (S != 0);

    // 先手・後手選択
    if(isFirst){
        cout << "First\n" << flush;
    } else {
        cout << "Second\n" << flush;
    }

    // 手番ループ
    bool ourTurn = isFirst;
    while(true){
        int i, x, ret;
        if(!ourTurn){
            // 相手の手番結果を読み込む
            cin >> i >> x;
            cin >> ret;
            if(ret <= 0) break;  // ret=−1: 負け / ret=1: 勝ち（相手がミス？） 
            --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 or 上のループで見つからなかったときは、有効な 1 以上の取りをする
            for(int j = 0; j < N; j++){
                if(A[j] > 0 && 1 <= K){
                    move_i = j;
                    move_x = 1;
                    break;
                }
            }
        }

        // 手を出力
        A[move_i] -= move_x;
        cout << (move_i+1) << " " << move_x << "\n" << flush;
        cin >> ret;
        if(ret != 0) break;  // ret=1: 勝ち ／ ret=−1: 負け
        K = move_x;
        ourTurn = false;
    }

    return 0;
}
0