#861687 (C++17) No.2278 Time Bomb Game 2

• 問題: No.2278 Time Bomb Game 2
• ユーザー: Ujjwal Rana
• 提出日時: 2023-04-21 22:45:54
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 11 ms / 2,000 ms
• コード長: 7,073 bytes
• コンパイル時間: 5,226 ms
• コンパイル使用メモリ: 264,756 KB
• 実行使用メモリ: 8,064 KB
• 最終ジャッジ日時: 2024-11-15 04:20:23
• 合計ジャッジ時間: 7,657 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,820 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	AC	2 ms; 6,816 KB
testcase_06	AC	3 ms; 6,816 KB
testcase_07	AC	7 ms; 6,816 KB
testcase_08	AC	7 ms; 6,820 KB
testcase_09	AC	9 ms; 7,552 KB
testcase_10	AC	9 ms; 8,064 KB
testcase_11	AC	9 ms; 7,936 KB
testcase_12	AC	8 ms; 7,936 KB
testcase_13	AC	10 ms; 7,936 KB
testcase_14	AC	10 ms; 8,064 KB
testcase_15	AC	10 ms; 7,936 KB
testcase_16	AC	9 ms; 8,064 KB
testcase_17	AC	9 ms; 7,936 KB
testcase_18	AC	9 ms; 8,064 KB
testcase_19	AC	10 ms; 7,936 KB
testcase_20	AC	9 ms; 8,064 KB
testcase_21	AC	9 ms; 7,936 KB
testcase_22	AC	9 ms; 7,936 KB
testcase_23	AC	10 ms; 8,064 KB
testcase_24	AC	10 ms; 7,936 KB
testcase_25	AC	10 ms; 7,936 KB
testcase_26	AC	10 ms; 7,936 KB
testcase_27	AC	10 ms; 8,064 KB
testcase_28	AC	9 ms; 8,064 KB
testcase_29	AC	9 ms; 7,936 KB
testcase_30	AC	10 ms; 7,936 KB
testcase_31	AC	9 ms; 7,936 KB
testcase_32	AC	9 ms; 8,064 KB
testcase_33	AC	9 ms; 8,064 KB
testcase_34	AC	10 ms; 7,936 KB
testcase_35	AC	10 ms; 7,936 KB
testcase_36	AC	9 ms; 8,064 KB
testcase_37	AC	9 ms; 7,936 KB
testcase_38	AC	10 ms; 8,064 KB
testcase_39	AC	10 ms; 7,936 KB
testcase_40	AC	9 ms; 7,936 KB
testcase_41	AC	10 ms; 7,936 KB
testcase_42	AC	8 ms; 8,064 KB
testcase_43	AC	9 ms; 7,936 KB
testcase_44	AC	10 ms; 8,064 KB
testcase_45	AC	10 ms; 7,936 KB
testcase_46	AC	9 ms; 7,936 KB
testcase_47	AC	9 ms; 8,064 KB
testcase_48	AC	10 ms; 7,936 KB
testcase_49	AC	10 ms; 7,936 KB
testcase_50	AC	9 ms; 8,064 KB
testcase_51	AC	10 ms; 8,064 KB
testcase_52	AC	8 ms; 7,936 KB
testcase_53	AC	10 ms; 7,936 KB
testcase_54	AC	8 ms; 7,936 KB
testcase_55	AC	9 ms; 8,064 KB
testcase_56	AC	9 ms; 7,936 KB
testcase_57	AC	9 ms; 7,936 KB
testcase_58	AC	9 ms; 8,064 KB
testcase_59	AC	10 ms; 8,064 KB
testcase_60	AC	10 ms; 7,936 KB
testcase_61	AC	9 ms; 7,936 KB
testcase_62	AC	11 ms; 7,936 KB
testcase_63	AC	9 ms; 7,936 KB
testcase_64	AC	9 ms; 8,064 KB
testcase_65	AC	9 ms; 8,064 KB
testcase_66	AC	9 ms; 7,936 KB
testcase_67	AC	8 ms; 7,936 KB
testcase_68	AC	8 ms; 7,936 KB
testcase_69	AC	9 ms; 7,936 KB
testcase_70	AC	9 ms; 8,064 KB
testcase_71	AC	2 ms; 6,816 KB

コンパイルメッセージ

main.cpp: In function 'bool solve()':
main.cpp:276:16: warning: 'okg' may be used uninitialized [-Wmaybe-uninitialized]
  276 |         a=t-abs(k-okg);
      |             ~~~^~~~~~~
main.cpp:239:8: note: 'okg' was declared here
  239 |     ll okg,ind;
      |        ^~~

ソースコード

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
typedef long long ll;
#define mod1 (ll)1000000007
#define mod2 (ll)998244353
#define pll pair<ll,ll>
typedef long double lb;
typedef tree<
pair<ll, ll>,
null_type,
less<pair<ll, ll>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
#define eps (lb)(1e-9)
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// Operator overloads
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }

template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
        cin >> it;
    return istream;
}

template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }

// Utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template <typename T, typename... Args>
void print(T &&t, Args &&... args)
{
    cout << t << " ";
    print(forward<Args>(args)...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll p){ // gives random number in [0,p]

 return uniform_int_distribution<ll>(0, p)(rng);
}

class DisjSet {
    vector<int>sz,parent; int n;

public:
       int connected;
    // Constructor to create and
    // initialize sets of n items
    DisjSet(int n)
    {
        sz = vector<int>(n,1);
        parent = sz;
        this->n = n;
        this->connected=n; 
        makeSet();
    }

    // Creates n single item sets
    void makeSet()
    {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // Finds set of given item x
    int find(int x)
    {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x) {

            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);

            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }

        return parent[x];
    }

    int size(int x)
    {
        return sz[find(x)];
    }
    // Do union of two sets represented
    // by x and y.
    void Union(int x, int y)
    {
        // Find current sets of x and y
        int xset = find(x);
        int yset = find(y);

        // If they are already in same set
        if (xset == yset){
            return;
        }

         connected--;
        // Put smaller ranked item under
        // bigger ranked item if ranks are
        // different
        if (sz[xset] <= sz[yset]) {
            parent[xset] = yset;
            sz[yset] += sz[xset];
        }
        else  {
            parent[yset] = xset;
            sz[xset] += sz[yset];
        }

    }
};
DisjSet dsu(2);
ll n,k,t;
vector<ll>v,las;
ll calc(ll ind,ll moves){ // it's on border and connected with other component
    // cout<<ind<<" "<<moves<<endl;
    if(moves<=0){
        return v[ind];
    }
    else if(moves==1){
        return v[ind]^1;
    }
    else if(moves%2==0 and dsu.size(ind)%2){
        return v[ind];
    }
    else if(dsu.size(ind)>1 and (moves%2)){
        return v[ind]^1;
    }
    else if(dsu.size(ind)==1){
        if((ind+1)<n){
            if(calc(ind+1,moves-1)!=v[ind]){
                return v[ind]^1;
            }
        }
        if((ind-1)>=0){
            if(calc(ind-1,moves-1)!=v[ind]){
                return v[ind]^1;
            }
        }
        return v[ind];
    }
    else if(dsu.find(ind)==dsu.find(0)){
        return v[ind];
    }
    else if(dsu.find(ind)==dsu.find(n-1)){
        return v[ind];
    }
    else if(v[ind-1]!=v[ind]){
        ll k=ind-1;
        for(ll j(ind);j<n;++j){
            if(dsu.find(j)!=dsu.find(ind)){
                k=j;
                break;
            }
        }
        if(moves>=(k-ind)){
            return v[ind]^1;
        }
        else{
            return v[ind];
        }
    }
    else{
        ll k=ind+1;
        for(ll j(ind);j>-1;--j){
            if(dsu.find(j)!=dsu.find(ind)){
                k=j;
                break;
            }
        }
        if(moves>=(ind-k)){
            return v[ind]^1;
        }
        else{
            return v[ind];
        }
    }
}
bool solve();
int main() {
io;
ll t=1,n=1;
// cin>>t;
while (t--){
    solve()?cout<<"Alice"<<endl:cout<<"Bob"<<endl;;
    }
     return 0;
}
bool solve(){
    cin>>n>>k>>t;
    v.resize(n);
    las=v;
    dsu=DisjSet(n);
    for(ll i(0);i<n;++i){
        char p;
        cin>>p;
        ll t=(p-'A');
        v[i]=t;
        if(i>0 and v[i]==v[i-1]){
            dsu.Union(i,i-1);
        }
    }
    ll a=t,b=t;
    ll okg,ind;
    if(dsu.connected==1){
        return v[0];
    }
    --k;
    if(dsu.find(n-1)==dsu.find(k)){
        for(ll t(k);t>-1;--t){
            if(dsu.find(k)!=dsu.find(t)){okg=t; break;}
        }
        okg++;
        a=t-abs(k-okg);
        ind=okg;
        if(calc(okg,a)!=v[ind]){
            return v[ind]^1;
        }
        return v[ind];
    }
    else if(dsu.find(0)==dsu.find(k)){
        for(ll t(k);t<n;++t){
            if(dsu.find(k)!=dsu.find(t)){okg=t; break;}
        }
        okg--;
        a=t-abs(k-okg);
        ind=okg;
        if(calc(okg,a)!=v[ind]){
            return v[ind]^1;
        }
        return v[ind];
    }
    else{
        
        
        for(ll t(k);t<n;++t){
            if(dsu.find(k)!=dsu.find(t)){okg=t; break;}
        }
        okg--;
        
        a=t-abs(k-okg);
        ind=okg;
        if(calc(okg,a)!=v[ind]){
            return v[ind]^1;
        }
        for(ll t(k);t>-1;--t){
            if(dsu.find(k)!=dsu.find(t)){okg=t; break;}
        }
        okg++;
        a=t-abs(k-okg);
        ind=okg;
        if(calc(okg,a)!=v[ind]){
            return v[ind]^1;
        }
        return v[ind];

    }




}
// Do not get stuck on a single approach for long, think of multiple ways