QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684797#7161. Guessing GameOccDreamer0 1ms3816kbC++142.5kb2024-10-28 15:57:472024-10-28 15:57:47

Judging History

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

  • [2024-10-28 15:57:47]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3816kb
  • [2024-10-28 15:57:47]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

const int B = 32; 
const int MAXN = 1e5 + 5;

int a[MAXN];
int p, n, subsum[MAXN], dep[MAXN];
int sum, bel[MAXN], idx[MAXN], b[MAXN];

bool mark[MAXN];

pair<int,int> c[MAXN]; 

mt19937 rnd(time(0));

inline void build(int p, int l, int r){
	subsum[p]=r-l+1;
	if(l==r) return dep[p]=1, void();
	int mid=(l+r)>>1;
	build(p<<1,l,mid), build(p<<1|1,mid+1,r); dep[p]=dep[p<<1]+1;
	return ;
}

inline int add(int p, int l, int r, int pos){
	subsum[p]--; int res=0;
	if(subsum[p]==0) res=dep[p];
	if(l==r) return res;
	int mid=(l+r)>>1;
	if(pos<=mid) res=max(add(p<<1,l,mid,pos),res);
	else res=max(add(p<<1|1,mid+1,r,pos),res);
	return res;
}

inline void solve1(){
	cout << 7 << endl; int sum=0;
	for(int i=0;i<B;++i) bel[i]=i/2; 
	for(int i=1;i<=n-B;++i){
		int x;
		cin >> x; sum+=x, sum%=65536;
		cout << 7 << endl; mark[x]=1, a[x]=7; 
	}
	int tot=0;
	for(int i=0;i<n;++i){
		if(mark[i]) continue;
		idx[i]=tot; b[tot]=i; ++tot;
	}
	build(1,0,B-1);
//	cerr << "sum=" << sum << endl;
	for(int i=1;i<=B;++i){
		int x; 
		cin >> x;
		int t=add(1,0,B-1,idx[x]);
//		cerr << "t=" << t << endl;
		if(t>1) cout << t+1 << endl, a[x]=t+1;
		else{
			if((sum>>bel[idx[x]])&1) t=2;
			cout << t << endl, a[x]=t; 
		}
	}
	int x; cin >> x; a[x]=7;
	return ;
}

inline void solve2(){
	//for(int i=0;i<n;++i) cin >> a[i];
	int tot7=0;
	for(int i=0;i<n;++i) tot7+=a[i]==7;
	if(n-tot7==B){
		int tot=0;
		for(int i=0;i<n;++i)
			if(a[i]==7) continue;
			else c[++tot]=make_pair(a[i],i);
		int l=1, r=B, now=6;
		while(l+1<r){
			int mid=(l+r)>>1, L=-1, R=-1;
			for(int i=l;i<=mid;++i) L=c[i].first==now?c[i].second:L;
			for(int i=mid+1;i<=r;++i) R=c[i].first==now?c[i].second:R;
			if(L==R){
				cout << L << ' ' << R << endl;
				return ; 
			}
			if(L==-1) r=mid-1;
			else l=mid+1; --now;
		}
		cout << c[l].second << ' ' << c[r].second << endl;
	}
	else{
		int s=0, tot=0, ss=0;
		for(int i=0;i<n;++i) s+=i, s%=65536;
		for(int i=0;i<n;++i){
			if(a[i]==7) continue;
			(s+=65536-i%65536)%=65536;
			if(a[i]==1) ++tot;
			if(a[i]==2) ss|=1<<tot, ++tot;
		}
		ss%=65536;
//		cerr << "sum=" << ss << endl;
		(s+=65536-ss)%=65536;
//		cerr << "lol" << endl;
		if(s+(1<<16)>n) cout << s << ' ' << s << endl;
		else cout << s << ' ' << s+(1<<16) << endl; 
	}
	return ;
}

int main(){
	freopen("guess.in","r",stdin);
//	freopen("guess.out","w",stdout);
	cin >> p >> n;	
	if(p==1) solve1();
	else solve2();	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3816kb

input:


output:

0 0

input:


output:

0 0

result:

wrong answer Token "WA" doesn't correspond to pattern "OK"