結果

問題 No.2278 Time Bomb Game 2
ユーザー georgejshgeorgejsh
提出日時 2023-04-22 00:47:11
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 7,006 bytes
コンパイル時間 2,678 ms
コンパイル使用メモリ 161,664 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-24 10:17:40
合計ジャッジ時間 5,097 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 6 ms
5,376 KB
testcase_14 AC 5 ms
5,376 KB
testcase_15 AC 6 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 4 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 4 ms
5,376 KB
testcase_24 AC 6 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 4 ms
5,376 KB
testcase_27 AC 5 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 4 ms
5,376 KB
testcase_30 AC 4 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 4 ms
5,376 KB
testcase_33 AC 5 ms
5,376 KB
testcase_34 AC 5 ms
5,376 KB
testcase_35 AC 5 ms
5,376 KB
testcase_36 AC 4 ms
5,376 KB
testcase_37 AC 4 ms
5,376 KB
testcase_38 AC 4 ms
5,376 KB
testcase_39 AC 5 ms
5,376 KB
testcase_40 AC 3 ms
5,376 KB
testcase_41 AC 4 ms
5,376 KB
testcase_42 AC 3 ms
5,376 KB
testcase_43 AC 4 ms
5,376 KB
testcase_44 AC 3 ms
5,376 KB
testcase_45 AC 3 ms
5,376 KB
testcase_46 AC 3 ms
5,376 KB
testcase_47 AC 4 ms
5,376 KB
testcase_48 AC 6 ms
5,376 KB
testcase_49 AC 4 ms
5,376 KB
testcase_50 AC 3 ms
5,376 KB
testcase_51 AC 5 ms
5,376 KB
testcase_52 AC 3 ms
5,376 KB
testcase_53 AC 4 ms
5,376 KB
testcase_54 AC 3 ms
5,376 KB
testcase_55 AC 4 ms
5,376 KB
testcase_56 AC 3 ms
5,376 KB
testcase_57 AC 4 ms
5,376 KB
testcase_58 AC 3 ms
5,376 KB
testcase_59 AC 5 ms
5,376 KB
testcase_60 AC 5 ms
5,376 KB
testcase_61 AC 3 ms
5,376 KB
testcase_62 AC 5 ms
5,376 KB
testcase_63 AC 3 ms
5,376 KB
testcase_64 AC 3 ms
5,376 KB
testcase_65 AC 3 ms
5,376 KB
testcase_66 AC 3 ms
5,376 KB
testcase_67 AC 3 ms
5,376 KB
testcase_68 AC 3 ms
5,376 KB
testcase_69 AC 3 ms
5,376 KB
testcase_70 AC 3 ms
5,376 KB
testcase_71 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


using namespace std;


typedef long long int ll;
typedef long double ld;

typedef pair<ll, ll> pi;
typedef pair<ld,ld> pd;

typedef vector<ll> vi;
typedef vector<ld> vd;
typedef vector<pi> vpi;

#define repab(i, a, b) for (ll i = (a); i < (b); i++)
#define repabs(i, a, b,s) for (ll i = (a); i < (b); i+=(s))
#define rep(i, a) for (ll i = 0; i < (a); i++)
#define rrepab(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define rrepabs(i,a,b,s) for (ll i = (b)-1; i >= (a); i-=(s))
#define rrep(i,a) for (ll i = (a)-1; i >= 0; i--)
#define iter(a, x) for (auto& a : x)
#define repeat(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, repabs, repab, rep)
#define F_ORRC(...) GET5(__VA_ARGS__, rrepabs, rrepab, rrep)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define FORR(...) F_ORRC(__VA_ARGS__)(__VA_ARGS__)
#define v(a) vector<array<ll,a>>
#define minheap(a) priority_queue<array<ll,a>,vector<array<ll,a>>,greater<array<ll,a>> >

#define rloop(n) int n;re(n);rep(i,n)
#define array(n) array<ll,n>
#define rea(arr,n) int n;re(n);vi arr(n);re(arr);

#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize


template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

namespace io {
     #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss);cerr<< "line: "<<__LINE__ <<" "; err(_it, args); cerr<<endl;}

    void err(istream_iterator<string> it) {}
    
    
   
    // TYPE ID (StackOverflow)
    template<class T> struct like_array : is_array<T>{};
    template<class T, size_t N> struct like_array<array<T,N>> : true_type{};
    template<class T> struct like_array<vector<T>> : true_type{};
    template<class T> bool is_like_array(const T& a) { return like_array<T>::value; }
    
    
    // INPUT 
    
    template<class T> void re(T& x) { cin >> x; }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest);
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
    
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.fi,p.se); }
    template<class T> void re(vector<T>& a) { rep(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { rep(i,SZ) re(a[i]); }
    template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a);
    template<class T> ostream& operator<<(ostream& os, const vector<T>& a);
    template<class T> ostream& operator<<(ostream& os, const set<T>& a) ;
    template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) ;
    // OUTPUT 
    
    template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {
        os << '{' << a.fi << ", " << a.se << '}'; return os;
    }
    template<class T> ostream& printArray(ostream& os, const T& a, int SZ) {
        os << '{';
        rep(i,SZ) {
            if (i) {
                os << ", ";
                if (is_like_array(a[i])) cout << " ";
            }
            os << a[i];
        }
        os << '}';
        return os;
    }
    template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) {
        return printArray(os,a,SZ);
    }
    template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
        return printArray(os,a,sz(a));
    }
    template<class T> ostream& operator<<(ostream& os, const set<T>& a) {
        os << vector<T>(all(a)); return os;
    }
    template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {
        os << vector<pair<T1,T2>>(all(a)); return os;
    }
    
    template<class T> void pr(const T& x) { cout << x << '\n'; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
        cout << first << ' '; pr(rest...); 
    }
    template<typename T, typename... Args>
    void err(istream_iterator<string> it, T a, Args... args) {
        cerr << *it << " = " << a<<" " ;
        err(++it, args...);
    }
    template<typename T>
    void pa(vector<T> &a,bool psize=true){
        if(psize) cout<<a.size()<<"\n";
        iter(x,a) cout<<x<<" ";
        cout<<"\n";
    }
}
using namespace io;

//const int MOD = 1000000007;
const int MOD = 998244353;
const ll INF = 1e18;
const int MX = 2e5+1;

#define yes cout<<"YES\n"
#define no cout<<"NO\n"
vector<pair<char,int>> findgroups(string s){
    pair<char,int> p;
    p.fi=s[0];
    p.se=1;
    vector<pair<char,int>> res;
    res.pb(p);
    repab(i,1,sz(s)){
        auto &x=res.back();
        if(x.fi==s[i]) x.se++;
        else {
            p.fi=s[i];
            p.se=1;
            res.pb(p);
        }
    }
    //res.pb(p);
    return res;

}
map<array(2),int > mp;
int find_ans(vector<pair<char,int>> &res,int i,int t,int pos){
    error(i,t,pos);
    if(t==1 && res[i].se==1) return true;
    if(t==0) return false; 
    if(res[i].se>1 && (t>=pos+1 || t>=(res[i].se-pos))){
        //error("here",res[i]);
        if(i!=0 && t-pos-1>=0 && (t-pos-1 )% 2==0) return true;
        if(i!=sz(res)-1 &&t-(res[i].se-pos)>=0 && (t-(res[i].se-pos) )% 2==0) return true;
    } 
    if(mp.find({i,pos})!=mp.end()){
        auto rest=mp[{i,pos}];
        if(t%(rest-t)==0) return false;
        else return true;
        //return true;
    }
    mp[{i,pos}]=t;
    bool ans=false;
    if(i!=0 && t>=pos+1) ans|=!find_ans(res,i-1,t-(pos+1),res[i-1].se-1);
    if(ans) return ans;
    if(i!=sz(res)-1 && t>=(res[i].se-pos)) ans|=!find_ans(res,i+1,t-(res[i].se-pos),0);
    return ans;
}
void solve(){
   int n,k,t;
   re(n,k,t);
   string s;
   re(s);
    auto res=findgroups(s);
    //error(res);
    if(sz(res)==1){
        if(res[0].fi=='A') cout<<"Bob\n";
        else cout<<"Alice\n";
        return;
    }
    int curr=0;k--;
    rep(i,sz(res)){
        auto &x=res[i];
        if(k<curr+x.se) {
            if(find_ans(res,i,t,k-curr)) {
                if(s[k]=='A')
                    cout<<"Alice\n";
                else cout<<"Bob\n";
            }else {
                if(s[k]=='B')
                    cout<<"Alice\n";
                else cout<<"Bob\n";
            }
            return;
        }
        curr+=x.se;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //rloop(t){
        solve();
    //}
    return 0;
}
0