#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 #include 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 typedef long double lb; typedef tree< pair, null_type, less>, 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 // cin >> pair istream& operator>>(istream &istream, pair &p) { return (istream >> p.first >> p.second); } template // cin >> vector istream& operator>>(istream &istream, vector &v) { for (auto &it : v) cin >> it; return istream; } template // cout << pair ostream& operator<<(ostream &ostream, const pair &p) { return (ostream << p.first << " " << p.second); } template // cout << vector ostream& operator<<(ostream &ostream, const vector &c) { for (auto &it : c) cout << it << " "; return ostream; } // Utility functions template void print(T &&t) { cout << t << "\n"; } template void print(T &&t, Args &&... args) { cout << t << " "; print(forward(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(0, p)(rng); } class DisjSet { vectorsz,parent; int n; public: int connected; // Constructor to create and // initialize sets of n items DisjSet(int n) { sz = vector(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; vectorv,las; ll calc(ll ind,ll moves){ // it's on border and connected with other component // cout<1 and (moves%2)){ return v[ind]^1; } else if(dsu.size(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=(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"<>n>>k>>t; v.resize(n); las=v; dsu=DisjSet(n); for(ll i(0);i>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-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