結果

問題 No.2278 Time Bomb Game 2
コンテスト
ユーザー Jeroen Op de Beek
提出日時 2023-04-21 22:34:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,044 bytes
コンパイル時間 1,677 ms
コンパイル使用メモリ 193,792 KB
最終ジャッジ日時 2025-02-12 12:10:32
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 69 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
/* starting, I can't reach a thing of the other colour in time
loss.
otherwise assume you can reach the other colour.
if my thing is 1 big:
Have to choose a side and recursively play it.
If again it is 1 big. If I win on parity, I won
If I lose on parity, other player can always play back, so this is just parity

Otherwise, my run of cells is >1, can waste moves mod 2.
If I can reach the other side with my parity I won.
If can't reach other side or parities both bad, other player can force me back, so I lose


*/
bool solve(string s, int k, int t, bool first=1) {
    if(t==0) return false;
    int n = s.size();
    if( (k==0 or s[k]!=s[k-1]) and (k==n-1 or s[k]!=s[k+1])) {
        if(!first) {
            if(t%2==1) return true;
            return false;
        }
        bool won=0;
        if(k) won|=!solve(s,k-1,t-1,0);
        if(k!=n-1) won|=!solve(s,k+1,t-1,0);
    }
    // can walk multiple
    int i=k, j =k;
    while(i>0 and s[i-1]==s[k]) i--;
    while(j<n-1 and s[j+1]==s[k]) ++j;
    bool won=0;
    auto dist = [&](int d) {
        if(d<=t and (t-d)%2==0) won=1;
    };
    if(i!=0) dist(k-i+1);
    if(j!=n-1) dist(j-k+1);
    return won;
}
int main() {
    int n,k,t; cin >> n >> k >> t;
    string s; cin >> s;
    --k;
    auto res = solve(s,k,t);
    bool awon = res ^ (s[k]=='B');
    cout << (awon?"Alice\n":"Bob\n");
    



}
0