QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#432797#8722. 卡牌游戏A_zjzjTL 0ms0kbC++142.3kb2024-06-07 17:49:032024-06-07 17:49:04

Judging History

你现在查看的是最新测评结果

  • [2024-06-07 17:49:04]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-07 17:49:03]
  • 提交

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

output:


result: