QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#432797 | #8722. 卡牌游戏 | A_zjzj | TL | 0ms | 0kb | C++14 | 2.3kb | 2024-06-07 17:49:03 | 2024-06-07 17:49:04 |
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e6+10;
int T,n,a[2][N];
map<tuple<int,int,vector<int>,vector<int>>,pair<int,int>>his;
int dfs(int op,int las=0){
auto cur=make_tuple(op,las,ary(a[0],1,n),ary(a[1],1,n));
if(his.count(cur))return his[cur].first;
for(int c:{0,1}){
if(count(a[c]+1,a[c]+1+n,0)==n)return his[cur]={c,0},c;
}
if(!las){
for(int i=1;i<=n;i++)if(a[op][i]){
a[op][i]--;
if(dfs(!op,i)==op)return a[op][i]++,his[cur]={op,i},op;
a[op][i]++;
}
return his[cur]={!op,0},!op;
}else{
if(dfs(!op,0)==op)return his[cur]={op,-1},op;
if(a[op][las]){
a[op][las]--;
if(dfs(!op,las)==op)return a[op][las]++,his[cur]={op,las},op;
a[op][las]++;
}
return his[cur]={!op,0},!op;
}
}
void get(){
scanf("%d",&n);
for(int c:{0,1}){
for(int i=1;i<=n;i++)scanf("%d",&a[c][i]);
}
for(int c:{0,1}){
for(int i=1;i<=n;i++){
a[c][i]=min(a[c][i],a[!c][i]+1);
}
}
vector<int>x,y,z;
for(int i=1;i<=n;i++){
if(a[0][i]==a[1][i])y.push_back(a[0][i]+a[1][i]);
else if(a[0][i]<a[1][i])x.push_back(a[0][i]+a[1][i]);
else z.push_back(a[0][i]+a[1][i]);
}
sort(all(x)),reverse(all(x));
if(x.size()>2)x.resize(2);
sort(all(y)),reverse(all(y));
if(y.size()>2)y.resize(2);
sort(all(z)),reverse(all(z));
if(z.size()>2)z.resize(2);
vector<int>num;
for(int t:x)num.push_back(t);
for(int t:y)num.push_back(t);
for(int t:z)num.push_back(t);
sort(all(num)),num.erase(unique(all(num)),num.end());
vector<int>trs;
int cur=0;
for(int x:num){
for(cur++;cur%2!=x%2;cur++);
trs.push_back(cur);
}
n=0;
for(int t:x){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=(t-1)/2,a[1][n]=(t+1)/2;
}
for(int t:y){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=t/2,a[1][n]=t/2;
}
for(int t:z){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=(t+1)/2,a[1][n]=(t-1)/2;
}
// debug(ary(a[0],1,n));
// debug(ary(a[1],1,n));
puts(dfs(0)?"Bob":"Alice");
}
int main(){
for(scanf("%d",&T);T--;)get();
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
5 1 100 100 2 1 1 1 1 2 1 1 0 1 3 1 1 4 5 1 4 10 116 104 101 114 101 32 97 114 101 32 102 105 118 101 32 99 97 115 101 115