結果

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

ソースコード

diff # 

//  Interactive Game Solver
//  ───────────────────────
//  最上位ビット戦略（MSB）で常に nim XOR を 0 に保つ。
//  K を越える最小の 2 冪 L を求め，Ai % L で Nim を張り直すと
//  通常 Nim と同値になることを利用する。

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

/*--- 2 の冪で K を超える最小 L を返す ------------------------------------*/
static inline int64 nextPow2(int64 K) {
    int64 L = 1;
    while (L <= K) L <<= 1;
    return L;
}

/*--- XOR(Ai % L) を計算 ---------------------------------------------------*/
static inline int64 xorMod(const vector<int64>& A, int64 L) {
    int64 x = 0;
    for (int64 v : A) x ^= (v % L);
    return x;
}

/*--- 1 手で負け局面に移す手 (idx,x) を求める．存在しないとき {-1,-1} --------*/
static pair<int,int64> winningMove(const vector<int64>& A, int64 K) {
    int64 L   = nextPow2(K);
    int64 nim = xorMod(A, L);
    if (nim == 0) return {-1, -1};           // 負け局面：任意合法手を後で作る

    int64 msb = 1LL << (63 - __builtin_clzll(nim));   // nim の MSB
    for (int i = 0; i < (int)A.size(); ++i) {
        int64 mod = A[i] % L;
        if (mod & msb) {
            int64 target = mod ^ nim;        // mod → target (< mod)
            int64 x = mod - target;          // 1 ≤ x ≤ L/2 ≤ K
            if (1 <= x && x <= K && x <= A[i]) return {i, x};
        }
    }
    return {-1, -1};                         // 通常来ない
}

/*--- 適当な合法手（負け局面用） ------------------------------------------*/
static pair<int,int64> fallbackMove(const vector<int64>& A, int64 K) {
    for (int i = 0; i < (int)A.size(); ++i)
        if (A[i] >= 1 && 1 <= K) return {i, 1};
    return {-1, -1};                         // すべて 0 ならゲームは終わっている
}

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

    /*--- 初期入力 ---------------------------------------------------------*/
    int N;
    if (!(cin >> N)) return 0;
    vector<int64> A(N);
    for (auto &v : A) cin >> v;

    /*--- 先手 or 後手 -----------------------------------------------------*/
    int64 initial_xor = 0;
    for (auto v : A) initial_xor ^= v;

    bool myTurn = (initial_xor != 0);        // xor≠0 なら先手必勝
    if (myTurn) {
        cout << "First"  << endl << flush;
    } else {
        cout << "Second" << endl << flush;
    }

    int64 K = (1LL << 60);                   // 10^100 の代わり（Ai ≤ 1e4 なので十分）

    /*--- ゲームループ -----------------------------------------------------*/
    while (true) {
        if (!myTurn) {                       // ―― ジャッジの手番 ――
            int idx_input;
            int64 x_input;
            if (!(cin >> idx_input >> x_input)) return 0;  // i, x
            int ret;
            cin >> ret;                      // 状態
            if (ret != 0) return 0;          // 勝敗確定

            int idx = idx_input - 1;
            A[idx] -= x_input;
            if (A[idx] == 0) {                           // 山が空なら削除
                A.erase(A.begin() + idx);
            }
            K = x_input;
        }

        /*―― 自分の手番 ――*/
        pair<int,int64> mv = winningMove(A, K);
        if (mv.first == -1) mv = fallbackMove(A, K);     // xor==0 など
        int idx = mv.first;
        int64 x = mv.second;

        cout << (idx + 1) << ' ' << x << endl << flush;
        A[idx] -= x;
        if (A[idx] == 0) {
            A.erase(A.begin() + idx);
        }
        K = x;

        int ret;
        cin >> ret;                      // ゲーム状態
        if (ret != 0) return 0;          // 1: 勝利, -1: 敗北

        myTurn = false;                  // 次はジャッジ
    }
}
0