結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー Kevgen
提出日時 2025-04-18 22:37:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,666 bytes
コンパイル時間 1,998 ms
コンパイル使用メモリ 199,792 KB
実行使用メモリ 46,972 KB
最終ジャッジ日時 2025-04-18 22:37:25
合計ジャッジ時間 8,548 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// custom hash for pair<ll,ll>
struct pair_hash {
    size_t operator()(pair<ll,ll> const& p) const noexcept {
        // splitmix64 on the two 64‑bit halves
        auto h1 = p.first + 0x9e3779b97f4a7c15;
        auto h2 = p.second;
        // combine
        return std::hash<ll>()(h1 ^ (h2 >> 1));
    }
};

unordered_map<pair<ll,ll>, bool, pair_hash> memo;

// returns true if the player to move with piles (a,b) can force a win
bool win(ll a, ll b) {
    if (a < b) 
        return !win(b, a);
    // if you can do a % b and it hits zero, you win immediately
    if (a % b == 0) 
        return true;
    auto key = make_pair(a, b);
    auto it = memo.find(key);
    if (it != memo.end()) 
        return it->second;

    // 1) Try the "mod" move
    ll r = a % b;
    if (!win(b, r)) {
        return memo[key] = true;
    }

    // 2) Try the "decrement" move: replace a by a-1
    //    then piles are (a-1, b), but roles swap: opponent sees (b, a-1)
    bool canWinByDec = false;
    if (a-1 < b) {
        // now b > a-1, so of (b, a-1) the current player wins iff win(a-1,b) is false
        // we need f(b,a-1)==false to be able to move there and win,
        // i.e. win(a-1,b)==true
        if (win(a-1, b)) 
            canWinByDec = true;
    } else {
        // b <= a-1, so we directly ask if f(b, a-1)==false
        if (!win(b, a-1))
            canWinByDec = true;
    }
    return memo[key] = canWinByDec;
}

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

    ll A, B;
    cin >> A >> B;

    cout << (win(A, B) ? "Alice\n" : "Bob\n");
    return 0;
}
0