Submission #34907

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<cassert>
#include<algorithm>
#include"grader.h"
#include"honest.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

void identify(int n){
	vector<int> group[2];
	group[0].push_back(0);
	int which=0; // どっちのグループに属すか
	rep(i,n-1){
		if(question(1,i,i+1)==0) which=1-which;
		group[which].push_back(i+1);
	}

	int q[100000];
	rep(i,n) q[i]=question(2,i,77);

	int n0=group[0].size(),n1=group[1].size();
	bool pttn0=false,pttn1=false;
	if(n1==0){
		pttn0=(count(q,q+n,n)==n);
		pttn1=(count(q,q+n,0)==0);
	}
	else{
		// group[0] が正直者と仮定
		pttn0=true;
		rep(i,n0) if(q[group[0][i]]!=n0) pttn0=false;

		// group[1] が正直者と仮定
		pttn1=true;
		rep(i,n1) if(q[group[1][i]]!=n1) pttn1=false;
	}

	if(pttn0 && pttn1) impossible();
	else if(pttn0) rep(k,2) rep(i,group[k].size()) answer(group[k][i],1-k);
	else if(pttn1) rep(k,2) rep(i,group[k].size()) answer(group[k][i], k );
	else assert(0);
}

Submission Info

Judge Result