Submission #71158197

---

Source Code Expand

#include<bits/stdc++.h>
//bool Mst;
using namespace std;
namespace wyzfastio
{
#ifndef LOCAL
	namespace __getchar{const int bufsize=1<<22;char buf[bufsize],*p1=buf,*p2=buf;inline char getchar(){return (p1==p2&&(p2=(p1=buf)+fread(buf,1,bufsize,stdin),p1==p2))?EOF:(*p1++);}}using __getchar::getchar;namespace __putchar{const int bufsize=1<<22;char buf[bufsize],*p=buf;inline void putchar(const char ch){if(p-buf==bufsize) fwrite(buf,1,bufsize,stdout),p=buf;*p++=ch;}inline void flush(){fwrite(buf,1,p-buf,stdout),p=buf;}}using __putchar::putchar;using __putchar::flush;namespace __flusher{struct Flusher{Flusher(){}~Flusher(){flush();}}flusher;}
#define endl "\n"
#else
	void flush(){}
#define endl wyzfastio::oshelper::_endl
#endif
	std::string bool_str[2]={"false","true"};int double_mx=12;struct istream{void tie([[maybe_unused]]int x){}};struct ostream{void tie([[maybe_unused]]int x){}};istream in;ostream out;
	istream &operator>>(istream &in,char &s){s=getchar();while(s==' '||s=='\n'||s=='\r')s=getchar();return in;}istream &operator>>(istream &in,std::string &s){char ch=getchar();s.clear();while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();while(!(ch==' '||ch=='\n'||ch=='\r'||ch==EOF))s+=ch,ch=getchar();return in;}istream &operator>>(istream &in,__int128 &x){char ch=getchar();int o=0;__int128 r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}istream &operator>>(istream &in,unsigned __int128 &x){char ch=getchar();__int128 r=0;while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=r;return in;}
	ostream &operator<<(ostream &out,const char x){putchar(x);return out;}ostream &operator<<(ostream &out,const char *s){while(*s!='\0'&&*s!=EOF)putchar(*s),s++;return out;}ostream &operator<<(ostream &out,std::string s){for(char ch:s)putchar(ch);return out;}ostream &operator<<(ostream &out,__int128 x){static int __stk[66];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}ostream &operator<<(ostream &out,unsigned __int128 x){static int __stk[66];int top=0;if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10),x/=10;while(top)putchar(__stk[--top]+'0');return out;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){char ch=getchar();int o=0;_Tp r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){int r;in>>r;x=r;return in;}template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,istream &>::type operator>>(istream &in,_Tp &x){_Tp r=0,p=1;int op=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')op=-op;ch=getchar();}while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}if(ch=='.'){ch=getchar();while(ch>='0'&&ch<='9')r+=(p*=0.1)*(ch-'0'),ch=getchar();}x=r*op;return in;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){static int __stk[33];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){out<<bool_str[x];return out;}template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,ostream &>::type operator<<(ostream &out,_Tp x){if(x<0)putchar('-'),x=-x;static int __stk[233];int top=0;for(int i=0;i<double_mx;i++)x*=10;x=std::floor(x+0.5);for(_Tp y;x>=1;)y=std::floor(x/10),__stk[top++]=x-y*10,x=y;while(top<=double_mx)__stk[top++]=0;while(top>double_mx)putchar(__stk[--top]+'0');putchar('.');while(top)putchar(__stk[--top]+'0');return out;}
	namespace oshelper{struct ostreamhelper{};struct endler{};endler _endl;ostreamhelper set_bool_str(const std::string str_false,const std::string str_true){bool_str[0]=str_false,bool_str[1]=str_true;return ostreamhelper();}ostreamhelper set_precision(int precision){double_mx=precision;return ostreamhelper();}ostream &operator<<(ostream &out,[[maybe_unused]]ostreamhelper outhelper){return out;}ostream &operator<<(ostream &out,[[maybe_unused]]endler _endl){out<<"\n",flush();return out;}}
#define cin wyzfastio::in
#define cout wyzfastio::out
}
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=2e5+5;
struct SAM
{
	struct __SAM_nd
	{
		map<int,int> ch;
		int link,len;
		__SAM_nd(){ch.clear(),len=link=0;}
	}node[N<<1];
	map<int,int> mp;
	int dp(int u)
	{
		if(mp.count(u)) return mp[u];
		mp[u]=0;
		for(auto [c,v]:node[u].ch) mp[u]|=!dp(v);
		return mp[u];
	}
	int sz,lst;
	void init(){node[0].ch.clear(),node[0].len=0,node[0].link=-1,sz=1,lst=0;mp.clear();}
	SAM(){init();}
	inline int nd()
	{
		return node[sz]=__SAM_nd(),sz++;
	}
	void insert(char c)
	{
		int cur=nd();
		node[cur].len=node[lst].len+1;
		int p=lst;
		while(p!=-1&&!node[p].ch.count(c)) node[p].ch[c]=cur,p=node[p].link;
		if(p==-1) node[cur].link=0;
		else
		{
			int q=node[p].ch[c];
			if(node[p].len+1==node[q].len) node[cur].link=q;
			else
			{
				int cl=nd();
				node[cl].len=node[p].len+1,node[cl].ch=node[q].ch,node[cl].link=node[q].link;
				while(p!=-1&&node[p].ch[c]==q) node[p].ch[c]=cl,p=node[p].link;
				node[q].link=node[cur].link=cl;
			}
		}
		lst=cur;
	}
}sam;
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int tc;cin>>tc;
	while(tc--) [&]()
	{
		sam.init();
		string s;cin>>s;
		for(char c:s) sam.insert(c);
		if(sam.dp(0)) cout<<"Alice\n";
		else cout<<"Bob\n";
	}();
	return 0;
}

Submission Info

Judge Result