結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 01:19:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,598 bytes
コンパイル時間 1,238 ms
コンパイル使用メモリ 85,036 KB
実行使用メモリ 76,836 KB
最終ジャッジ日時 2025-04-19 01:19:18
合計ジャッジ時間 5,234 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <utility>
#include <algorithm>

using ll = long long;

std::map<std::pair<ll, ll>, bool> memo;

bool can_win(ll a, ll b);

bool can_win_mod(ll a, ll b) {
    if (a < b) return false;
    return !can_win(b, a % b);
}

bool can_win_minus_one(ll a, ll b) {
    if (a <= 0) return false;
    return !can_win(b, a - 1);
}

bool can_win(ll a, ll b) {
    if (a < b) {
        return !can_win(b, a);
    }
    if (a <= 0) {
        return false;
    }
     if (b <= 0) {
         return false;
     }

    std::pair<ll, ll> state = {a, b};
    if (memo.count(state)) {
        return memo[state];
    }

    if (a >= 2 * b) {
        memo[state] = true;
        return true;
    }

    ll d = a - b; // 差值 d = a - b

    if (!can_win(b, d)) {
        memo[state] = true;
        return true;
    }

    ll low = 0, high = b;
    ll k = b; 

    while (low <= high) {
        ll mid = low + (high - low) / 2;
        if (b - mid <= 0) { 
            k = mid;
            high = mid - 1;
        } else {
            if (!can_win(b - mid, d)) { 
                k = mid;
                high = mid - 1;
            } else { 
                low = mid + 1;
            }
        }
    }
   
    memo[state] = !can_win(b - k, a - k);
    return memo[state];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ll a, b;
    std::cin >> a >> b;

    if (can_win(a, b)) {
        std::cout << "Alice" << std::endl;
    } else {
        std::cout << "Bob" << std::endl;
    }

    return 0;
}
0