結果
問題 | No.1506 Unbalanced Pocky Game |
ユーザー | penguinman |
提出日時 | 2021-05-14 22:09:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 25,932 bytes |
コンパイル時間 | 2,497 ms |
コンパイル使用メモリ | 228,900 KB |
最終ジャッジ日時 | 2025-01-21 11:13:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,824 KB |
testcase_04 | AC | 8 ms
6,820 KB |
testcase_05 | AC | 10 ms
6,820 KB |
testcase_06 | AC | 7 ms
6,824 KB |
testcase_07 | AC | 5 ms
6,820 KB |
testcase_08 | AC | 6 ms
6,816 KB |
testcase_09 | AC | 11 ms
6,816 KB |
testcase_10 | AC | 9 ms
6,820 KB |
testcase_11 | AC | 5 ms
6,816 KB |
testcase_12 | AC | 4 ms
6,820 KB |
testcase_13 | AC | 3 ms
6,816 KB |
testcase_14 | AC | 35 ms
6,820 KB |
testcase_15 | AC | 5 ms
6,816 KB |
testcase_16 | AC | 10 ms
6,820 KB |
testcase_17 | AC | 5 ms
6,820 KB |
testcase_18 | AC | 4 ms
6,820 KB |
testcase_19 | AC | 3 ms
6,820 KB |
testcase_20 | AC | 11 ms
6,820 KB |
testcase_21 | AC | 5 ms
6,816 KB |
testcase_22 | AC | 7 ms
6,816 KB |
testcase_23 | AC | 1 ms
6,820 KB |
testcase_24 | AC | 1 ms
6,820 KB |
testcase_25 | AC | 14 ms
6,820 KB |
testcase_26 | AC | 19 ms
6,824 KB |
testcase_27 | AC | 20 ms
6,820 KB |
testcase_28 | AC | 18 ms
6,824 KB |
testcase_29 | AC | 17 ms
6,824 KB |
testcase_30 | AC | 18 ms
6,816 KB |
testcase_31 | AC | 20 ms
6,816 KB |
testcase_32 | AC | 17 ms
6,820 KB |
testcase_33 | AC | 18 ms
6,820 KB |
testcase_34 | AC | 18 ms
6,824 KB |
testcase_35 | AC | 17 ms
6,820 KB |
testcase_36 | AC | 1 ms
6,816 KB |
testcase_37 | AC | 1 ms
6,820 KB |
testcase_38 | AC | 1 ms
6,820 KB |
testcase_39 | AC | 1 ms
6,816 KB |
testcase_40 | AC | 2 ms
6,816 KB |
testcase_41 | AC | 3 ms
6,820 KB |
testcase_42 | AC | 2 ms
6,820 KB |
testcase_43 | AC | 1 ms
6,820 KB |
testcase_44 | AC | 2 ms
6,816 KB |
testcase_45 | AC | 1 ms
6,816 KB |
testcase_46 | AC | 8 ms
6,820 KB |
testcase_47 | AC | 3 ms
6,816 KB |
testcase_48 | AC | 4 ms
6,824 KB |
testcase_49 | AC | 9 ms
6,816 KB |
testcase_50 | AC | 7 ms
6,820 KB |
testcase_51 | AC | 9 ms
6,824 KB |
testcase_52 | AC | 7 ms
6,820 KB |
testcase_53 | AC | 9 ms
6,816 KB |
testcase_54 | AC | 5 ms
6,816 KB |
testcase_55 | AC | 3 ms
6,820 KB |
testcase_56 | AC | 37 ms
6,816 KB |
testcase_57 | AC | 8 ms
6,816 KB |
testcase_58 | AC | 3 ms
6,816 KB |
testcase_59 | AC | 3 ms
6,816 KB |
testcase_60 | AC | 6 ms
6,820 KB |
testcase_61 | AC | 7 ms
6,816 KB |
testcase_62 | AC | 6 ms
6,824 KB |
testcase_63 | AC | 5 ms
6,820 KB |
testcase_64 | AC | 8 ms
6,816 KB |
testcase_65 | AC | 5 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h>//using namespace std;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define rep(i, j, n) for(ll i = ll(j); i < ll(n); i++)#define REP(i, j, n) for(ll i = ll(j); i <= ll(n); i++)#define per(i, j, n) for(ll i = ll(j); ll(n) <= i; i--)#define ALL(a) (a).begin(),(a).end()#define revALL(a) (a).rbegin(),(a).rend()#define pb emplace_back#define mp std::make_pair#define mtp std::make_tuple#define ln "\n"using std::endl;using std::cin;using std::cout;using ll = long long;using lint = __int128;using std::vector;using std::string;using std::upper_bound;using std::lower_bound;using vi = vector<ll>;using vii = vector<vi>;using pii = std::pair<ll, ll>;using vs = vector<int>;using vss = vector<vs>;using pss = std::pair<int, int>;using vl = vector<lint>;using vll = vector<vl>;using pll = std::pair<lint, lint>;//constexpr ll MOD = 1e9+7, root = 0;//constexpr ll MOD = 998244353, root = 3;//constexpr ll MOD = 924844033, root = 5;//constexpr ll MOD = 1e4, root = 0;//constexpr ll MOD = 1e5, root = 0;//constexpr ll MOD = 1e6, root = 0;//constexpr ll MOD = 1e7, root = 0;constexpr ll MAX = 1e6+10;constexpr ll inf = (1ll << 60);constexpr lint linf = lint(inf) * inf;//lint outputvoid lout(lint N, string add){string S;if(N < 0){S += '-';N = -N;}string T;if(N == 0) T += '0';while(N){T += N % 10 + '0';N /= 10;}reverse(ALL(T));S += T;cout << S << add;}//lint inputlint lin(){string S; cin >> S;bool flag = 0;if(S[0] == '-') flag = 1;lint ret = 0;rep(i, flag, S.size()) ret = ret * 10 + S[i] - '0';if(flag) ret *= -1;return ret;}//reversed priority_queuetemplate<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};//modpowll modpow(ll X, ll Y, ll mod){ll ret = 1;while(Y){if(Y & 1){ret *= X;ret %= mod;}X *= X;X %= mod;Y >>= 1;}return ret % mod;}//calc: ax + by = gcd(a, b)template<typename T>void extGCD(ll a, ll b, T &x, T &y){if(b == 0){x = 1;y = 0;return;}extGCD(b, a%b, y, x);/*(a-b)x + by = gcd(a,b)ax + b(y-x) = gcd(a,b)*/y -= a / b * x;}//calc: ax + by = ctemplate<typename T>bool solve_equation(ll a, ll b, ll c, T &x, T &y){ll d = std::__gcd(a, b);if(c % d) return false;extGCD(a, b, x, y);ll e = a * b / d;x %= e;y %= e;x = (lint)x * (c/d) % e;y = (lint)y * (c/d) % e;return true;}//segment_tree, 1-indexedtemplate<typename T>struct segment_tree{ll N;T INF;vector<T> node;segment_tree(vector<T> &X, T INF_):INF(INF_){N = 1;while(N < X.size()) N <<= 1;node.resize(2*N, INF);rep(i, 0, X.size()) node[N+i] = X[i];per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);}T compare(T A, T B){return std::max(A, B);}//for max_right, min_left//compare をいじった時にはこちらも変えた方がよいbool is_lower(T A, T B){return A < B;}//isAdd == true: add//isAdd == false: updatevoid update(ll index, T val, bool isAdd){index += N;if(isAdd) node[index] += val;else node[index] = val;while(index > 0){index >>= 1;node[index] = compare(node[index*2], node[index*2+1]);}}T calc(ll left, ll right){T ret = INF;left += N;right += N;while(left < right){if(left & 1) ret = compare(node[left++], ret);if(right & 1) ret = compare(node[--right], ret);left >>= 1;right >>= 1;}return ret;}//[left, inf)ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){if(r < 0) r = N;if(is_lower(node[now], val) || r<=left) return r;if(N <= now) return l;ll vl = min_left(left, val, now*2, l, (l+r)/2);if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);return vl;}//(-inf, right]//内部では (-inf, right+1)ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){if(r < 0) r = N, right++;if(is_lower(node[now], val) || right<=l) return l-1;if(N <= now) return l;ll vr = max_right(right, val, now*2+1, (l+r)/2, r);if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);return vr;}};//lazy_segment_treetemplate<typename T>struct lazy_segment_tree{int N, height;vector<T> node, lazy;T valINF, lazyINF;lazy_segment_tree(vector<T> X, T valINF_, T lazyINF_) : valINF(valINF_), lazyINF(lazyINF_){N = 1, height = 0;while(N < X.size()) N <<= 1, height++;node.resize(2*N, valINF);lazy.resize(2*N, lazyINF);rep(i, 0, X.size()) node[i+N] = X[i];per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);}void add(ll left, ll right, T val){ll l = left+N, r = right+N;ll L = l, R = r;per(i, height, 0){eval(l >> i);eval(r >> i);}while(l < r){if(l & 1){addition(lazy[l], val);l++;}if(r & 1){r--;addition(lazy[r], val);}l >>= 1;r >>= 1;}while(L){if(lazy[L]==lazyINF && L<N){eval(L*2);eval(L*2+1);node[L] = compare(node[L*2], node[L*2+1]);}if(lazy[R]==lazyINF && R<N){eval(R*2);eval(R*2+1);node[R] = compare(node[R*2], node[R*2+1]);}L >>= 1;R >>= 1;}}T calc(ll left, ll right){ll l = left+N, r = right+N;per(i, height, 0){eval(l >> i);eval(r >> i);}T ret = valINF;while(l < r){if(l & 1){eval(l);ret = compare(node[l], ret);l++;}if(r & 1){r--;eval(r);ret = compare(node[r], ret);}l >>= 1;r >>= 1;}return ret;}//[left, inf)ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){if(r < 0) r = N;eval(now);if(is_lower(node[now], val) || r<=left) return r;if(N <= now) return l;ll vl = min_left(left, val, now*2, l, (l+r)/2);if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);return vl;}//(-inf, right]//内部では (-inf, right+1)ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){if(r < 0) r = N, right++;eval(now);if(is_lower(node[now], val) || right<=l) return l-1;if(N <= now) return l;ll vr = max_right(right, val, now*2+1, (l+r)/2, r);if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);return vr;}private:T compare(T A, T B){return std::max(A, B);}//for max_right, min_left//compare をいじった時にはこちらも変えた方がよいbool is_lower(T A, T B){return A < B;}void addition(T &A, T B){//addition :A += B;//update : A = B;}void eval(int now){if(lazy[now] == lazyINF) return;if(now < N){addition(lazy[now*2], lazy[now]);addition(lazy[now*2+1], lazy[now]);}addition(node[now], lazy[now]);lazy[now] = lazyINF;}};//union_find_treestruct union_find{ll N;vi par, siz;union_find(int n) : N(n){par.resize(N);siz.resize(N, 1);rep(i,0,N) par[i] = i;}ll root(ll X){if(par[X] == X) return X;return par[X] = root(par[X]);}bool same(ll X, ll Y){return root(X) == root(Y);}void unite(ll X, ll Y){X = root(X);Y = root(Y);if(X == Y) return;if(siz[Y] < siz[X]) std::swap(X, Y);par[X] = Y;siz[Y] += siz[X];siz[X] = 0;}ll size(ll X){return siz[root(X)];}};//binary_indexed_treetemplate<typename T>struct binary_indexed_tree{int N;vector<T> bit;binary_indexed_tree(int n):N(n){bit.resize(N+1,0);}T addition(T a, T b){return a+b;}void add(int x,T a){x++;for(x; x<=N; x+=(x&-x)) bit[x] = addition(bit[x], a);}T sum(int x){x++;T ret=0;for(x; x>0; x-=(x&-x)) ret = addition(ret, bit[x]);return ret;}ll lower_bound(T X){if(sum(N)<X) return -1;ll ret=0, memo=1;T sum=0;while(memo*2 <= N) memo *= 2;while(0 < memo){if(memo+ret<=N && addition(sum, bit[memo+ret])<X){sum = addition(sum, bit[memo+ret]);ret+=memo;}memo/=2;}return ret;}};//directed_graghstruct directed_gragh{ll N, M;vii edge;directed_gragh(vii e) : edge(e){N = edge.size();rep(i,0,N) M += edge[i].size();}vi sort(){vi ret, cnt(N);rep(i,0,N){for(auto p:edge[i]) cnt[p]++;}std::queue<ll> que;rep(i,0,N){if(cnt[i] == 0) que.push(i);}while(!que.empty()){ll now = que.front(); que.pop();ret.pb(now);for(auto next:edge[now]){cnt[next]--;if(cnt[next] == 0) que.push(next);}}return ret;}vii SCC(){vii revedge(N), ver;vi ind(N);rep(i,0,N){for(auto p:edge[i]) revedge[p].pb(i);}vi num(N, -1), po(N);vector<bool> seen(N);ll cnt = 0;rep(i,0,N){if(num[i] == -1){dfs(i, num, cnt);}}rep(i,0,N) po[num[i]] = i;per(i,N-1,0){ll X = po[i];if(!seen[X]){std::queue<ll> que;vi v;que.push(X);seen[X] = 1;while(!que.empty()){ll now = que.front(); que.pop();v.pb(now);ind[now] = ver.size();for(auto p:revedge[now]){if(!seen[p]){seen[p] = 1;que.push(p);}}}ver.pb(v);}}return ver;}void dfs(ll now, vi &num, ll &cnt){num[now] = 0;for(auto next:edge[now]){if(num[next] == -1){dfs(next, num, cnt);}}num[now] = cnt++;}};//sparse_tabletemplate<typename T>struct sparse_table{ll N;T INF;vector<T> A;vi mem;vector<vector<T>> table;std::function<T (T, T)> compare;sparse_table(vector<T> X, T INF_, std::function<T (T, T)> compare_) : A(X), INF(INF_), compare(compare_){N = A.size();mem.resize(N+1, -1);int height = 0;while((1<<height) <= N+1){mem[1<<height] = height;height++;}table.resize(N, vector<T>(height, INF));rep(i,0,N) table[i][0] = A[i];rep(j,1,height){rep(i,0,N){table[i][j] = compare(table[i][j-1], table[std::min(N-1, i+(1ll<<(j-1)))][j-1]);}}REP(i,1,N){mem[i] = std::max(mem[i-1], mem[i]);}}//[l, r)T calc(ll l, ll r){ll width = r-l;return compare(table[l][mem[width]], table[r-(1<<mem[width])][mem[width]]);}};//treestruct tree{int N, root;vii dp;vi par;vi dist;vi subtree;vii edge;tree(vii E, ll root_) : edge(E), root(root_){N=edge.size();dp.resize(N);par.resize(N);dist.resize(N,-1);for(int i=0;i<N;i++) dp[i].resize(20);dist[0]=dp[0][0]=0;std::queue<int> que;que.push(0);while(!que.empty()){int now=que.front(); que.pop();for(int i=0;i<edge[now].size();i++){int next=edge[now][i];if(dist[next]==-1){dist[next]=dist[now]+1;que.push(next);par[next]=now;dp[next][0]=now;}}}for(int i=1;i<20;i++){for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];}}int LCA(int X,int Y){if(dist[X]<dist[Y]) std::swap(X,Y);{int Z=dist[X]-dist[Y];int i=0;while(Z){if(Z&1) X=dp[X][i];i++;Z>>=1;}}if(X==Y) return X;for(int i=19;i>=0;i--){if(dp[X][i]!=dp[Y][i]){X=dp[X][i];Y=dp[Y][i];}}return dp[X][0];}void Subtree(){subtree.resize(N,-1);dfs(0);}void dfs(ll now){subtree[now]=1;for(auto next:edge[now]){if(subtree[next]==-1){dfs(next);subtree[now]+=subtree[next];}}}};//max_flowtemplate<typename T>struct max_flow{struct Edge{int to;T cap;int rev;};int N;vector<vector<Edge>> edge;vector<int> dist,itr;max_flow(vii e,vii w){N=e.size();edge.resize(N);rep(i,0,N){rep(j,0,e[i].size()){edge[i].pb((Edge){(int)e[i][j],(T)w[i][j],(int)edge[e[i][j]].size()});edge[e[i][j]].pb((Edge){i,0,(int)edge[i].size()-1});}}}void add_edge(int from,int to,T cap){edge[from].pb((Edge){to,cap,(int)edge[to].size()});edge[to].pb((Edge){from,0,(int)edge[from].size()-1});}void bfs(int s){dist.assign(N,-1);std::queue<int> que;dist[s]=0;que.push(s);while(!que.empty()){int now=que.front(); que.pop();for(auto p:edge[now]){int next=p.to;if(p.cap>0&&dist[next]<0){dist[next]=dist[now]+1;que.push(next);}}}}T dfs(int now,int t,T f){if(now==t) return f;for(;itr[now]<edge[now].size();itr[now]++){Edge& p=edge[now][itr[now]];if(p.cap>0&&dist[now]<dist[p.to]){T mem=dfs(p.to,t,std::min(f,p.cap));if(mem>0){p.cap-=mem;edge[p.to][p.rev].cap+=mem;return mem;}}}return 0;}T Query(int s,int t){T ret=0;while(1){bfs(s);if(dist[t]<0) break;itr.assign(N,0);while(1){int mem=dfs(s,t,(1<<30));if(mem<=0) break;ret+=mem;}}return ret;}};//min_cost_flowstruct min_cost_flow{struct Edge{int to,cap,rev;ll cost;};int N;vector<vector<Edge>> edge;vector<ll> dist,h;void add_edge(int from,int to,int cap,ll cost){edge[from].pb((Edge){to,cap,(int)edge[to].size(),cost});edge[to].pb((Edge){from,0,(int)edge[from].size()-1,-cost});}min_cost_flow(vii e,vii m,vii w){N=e.size();edge.resize(N);rep(i,0,N){rep(j,0,e[i].size()){add_edge(i,e[i][j],m[i][j],w[i][j]);}}}void potential(){h.assign(N,0);vector<vector<int>> edge2(N);vii weight(N);vector<int> cnt(N);rep(i,0,N){for(auto e:edge[i]){if(e.cap>0&&e.cost<0){edge2[i].pb(e.to);weight[i].pb(-e.cost);cnt[e.to]++;}}}std::queue<ll> que;rep(i,0,N){if(cnt[i]==0) que.push(i);}vector<int> ver;while(!que.empty()){int now=que.front(); que.pop();ver.pb(now);for(auto next:edge2[now]){cnt[next]--;if(cnt[next]==0) que.push(next);}}per(i,N-1,0){rep(j,0,edge2[ver[i]].size()){int next=edge2[ver[i]][j];h[ver[i]]=std::max(h[ver[i]],h[next]+weight[ver[i]][j]);}}}ll Query(int s,int t,int f){ll ret=0;potential();while(f){vi dist(N,inf);vector<int> memv(N),meme(N);dist[s]=0;prique<std::pair<ll,int>> que;que.push(mp(0,s));while(!que.empty()){auto now=que.top().second;if(dist[now]<que.top().first){que.pop();continue;}que.pop();rep(i,0,edge[now].size()){auto e=edge[now][i];auto next=e.to;if(e.cap>0&&dist[next]>dist[now]+h[now]-h[next]+e.cost){dist[next]=dist[now]+h[now]-h[next]+e.cost;memv[next]=now;meme[next]=i;que.push(mp(dist[next],next));}}}if(dist[t]==inf) return -1;int now=t,max=f;while(now!=s){auto& e=edge[memv[now]][meme[now]];max=std::min(max,e.cap);now=memv[now];}f-=max;now=t;while(now!=s){auto& e=edge[memv[now]][meme[now]];e.cap-=max;auto& e2=edge[e.to][e.rev];e2.cap+=max;now=memv[now];}rep(i,0,N) h[i]+=dist[i];ret+=h[t]*max;}return ret;}};//fftstruct Fast_Fourier_Transform{void dft(vector<std::complex<double>> &func,int inverse){int siz=func.size();if(siz==1) return;vector<std::complex<double>> left,right;rep(i,0,siz/2){left.pb(func[i*2]);right.pb(func[i*2+1]);}dft(left,inverse);dft(right,inverse);std::complex<double> now=1,zeta=std::polar(1.0,inverse*2.0*acos(-1)/siz);rep(i,0,siz){func[i]=left[i%(siz/2)]+now*right[i%(siz/2)];now*=zeta;}}template<typename T>vector<double> multiply(vector<T> f,vector<T> g){vector<std::complex<double>> nf,ng;int siz=1;while(siz<f.size()+g.size()) siz<<=1;nf.resize(siz);ng.resize(siz);rep(i,0,f.size()) nf[i]=f[i];rep(i,0,g.size()) ng[i]=g[i];dft(nf,1);dft(ng,1);rep(i,0,siz) nf[i]*=ng[i];dft(nf,-1);vector<double> ret(siz);rep(i,0,siz) ret[i]=nf[i].real()/siz;return ret;}};//nttstruct Numver_Theoretic_Transform{vii mem;Numver_Theoretic_Transform(void){mem.resize(25,vi(2));rep(i,0,25){mem[i][1]=modpow(root,MOD-1-(MOD-1)/(1<<i),MOD);mem[i][0]=modpow(root,(MOD-1)/(1<<i),MOD);}}void dft(vi &func,bool inverse,ll cnt){int siz=func.size();if(siz==1) return;vi left,right;rep(i,0,siz/2){left.pb(func[i*2]);right.pb(func[i*2+1]);}dft(left,inverse,cnt-1);dft(right,inverse,cnt-1);ll now=1;ll zeta=mem[cnt][inverse];rep(i,0,siz){func[i]=(left[i%(siz/2)]+now*right[i%(siz/2)])%MOD;now*=zeta;now%=MOD;}}vi multiply(vi f,vi g){ll cnt=0;vi nf,ng;int siz=1;while(siz<f.size()+g.size()){cnt++;siz<<=1;}nf.resize(siz);ng.resize(siz);rep(i,0,f.size()) nf[i]=f[i];rep(i,0,g.size()) ng[i]=g[i];dft(nf,0,cnt);dft(ng,0,cnt);rep(i,0,siz){nf[i]*=ng[i];nf[i]%=MOD;}dft(nf,1,cnt);vi ret(siz);ll div=modpow(siz,MOD-2,MOD);rep(i,0,siz) ret[i]=nf[i]*div%MOD;return ret;}};//triestruct Trie{int let;char lower;vector<int> cnt;vector<vector<int>> next;Trie(int element,char low):let(element),lower(low){cnt.resize(1);next.pb(vector<int>(let,-1));}void insert(string S){int now=0;for(auto s:S){int X=s-lower;if(next[now][X]==-1){next[now][X]=cnt.size();cnt.pb(0);next.pb(vector<int>(lower,-1));}now=next[now][X];}cnt[now]++;}int get(string S){int now=0;for(auto s:S){int X=s-lower;if(next[now][X]==-1) return 0;now=next[now][X];}return cnt[now];}};//pointtemplate<typename T>struct point{T x,y;void operator+=(const point &other){x += other.x;y += other.y;}void operator-=(const point &other){x -= other.x;y -= other.y;}bool operator<(const point &other){if(x == other.x) return y < other.y;return x < other.x;}bool operator==(const point &other){return x==other.x && y==other.y;}};//偏角の比較を整数でtemplate<typename T>struct tancomp{int place(point<T> p){if(p.x<=0&&p.y<0) return 0;if(p.x>0&&p.y<=0) return 1;if(p.x==0&&p.y==0) return 2;if(p.x>=0&&p.y>0) return 3;return 4;}bool operator()(const point<T> &l,const point<T> &r){if(place(l)!=place(r)) return place(l)<place(r);//l.second/l.first<r.second/r.firstreturn l.y*r.x < l.x*r.y;}};//xor の基底 (base)vi get_bases(vi A,ll max_digit){int now=0;int N=A.size();per(i,max_digit,0){rep(j,now,N){if(A[j]&(1ll<<i)){std::swap(A[j],A[now]);break;}}if(now<N&&A[now]&(1ll<<i)){rep(j,0,N){if(j!=now&&A[j]&(1ll<<i)) A[j]^=A[now];}now++;}}vi bases;rep(i,0,now) bases.pb(A[i]);return bases;}//convex_hull, 凸 は 180° 以下と定義template<typename T>vi convex_hull(vector<point<T>> A){ll N = A.size();vector<std::pair<point<T>,ll>> data(N);rep(i,0,N) data[i] = mp(A[i],i);sort(ALL(data),[](std::pair<point<T>,ll> l,std::pair<point<T>,ll> r){if(l.first == r.first) return l.second < r.second;return l.first < r.first;});vi ret;ret.pb(0);//lowerrep(i,1,data.size()){while(ret.size() > 1){ll n = ret.size();point<T> A = data[ret[n-2]].first;point<T> B = data[ret[n-1]].first;point<T> C = data[i].first;B -= A;C -= A;if(B.x*C.y-B.y*C.x < 0) ret.pop_back();else break;}ret.pb(i);}//upperper(i,int(data.size())-2,0){while(ret.size() > 1){ll n = ret.size();point<T> A = data[ret[n-2]].first;point<T> B = data[ret[n-1]].first;point<T> C = data[i].first;B -= A;C -= A;if(B.x*C.y-B.y*C.x < 0) ret.pop_back();else break;}ret.pb(i);}ret.pop_back();for(auto &p:ret) p = data[p].second;return ret;}//binom_init, binomvi fac,finv,inv;void binom_init() {fac.resize(MAX);finv.resize(MAX);inv.resize(MAX);fac[0] = fac[1] = 1;inv[1] = 1;finv[0] = finv[1] = 1;rep(i, 2, MAX){fac[i] = fac[i-1]*i%MOD;inv[i] = MOD-MOD/i*inv[MOD%i]%MOD;finv[i] = finv[i-1]*inv[i]%MOD;}}ll binom(ll n, ll r){if(n<r || n<0 || r<0) return 0;return fac[n]*finv[r]%MOD*finv[n-r]%MOD;}//compressionvoid comp(vi &A){std::map<ll,ll> memo;rep(i,0,A.size()) memo[A[i]]=0;ll cnt=0;for(auto &p:memo) p.second=cnt++;rep(i,0,A.size()) A[i]=memo[A[i]];}//decrease the value of mapvoid dec(std::map<ll,ll> &mem,ll X){mem[X]--;if(mem[X]==0) mem.erase(X);}//mainint main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::random_device rnd;std::mt19937 mt(rnd());ll N; cin >> N;vi A(N);rep(i,0,N) cin >> A[i];string ans = "Bob";while(A.size()>1 && A[A.size()-1]==1) A.pop_back();if((N-A.size())%2 == 0) ans = "Alice";cout << ans << ln;}