Submission #142583

---

Source Code Expand

#include "grader.h"
#include "honest.h"


#include <cstdio>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)

vector<int> dat[100005];

vector<int> ok;
int gone[100005]={};

/*
int question(int a,int b,int c){
  if(a==1)printf("to..%d is..%d?\n",b,c);
  else printf("to..%d how?\n",b);
  scanf("%d",&a);
  return a;
}
void answer(int p,int q){
  printf("%d..%s\n",p,q==1?"honest":"liar");
}
void impossible(){printf("impossible\n");}
*/

void identify(int N){
  int isnone=0;
  rep(i,N){
    int a=question(2,i,0);
    if(a==0)isnone=1;
    if(1<=a && a<=N)dat[a].push_back(i);
  }
  
  reg(i,1,N){
    if(dat[i].size()==i)ok.push_back(i);
  }
  int hone=-1;
  
  if(ok.size()==1){
    if(isnone==1)hone=ok[0];
    else{
      impossible();
      return;
    }
  }
  else if(ok.size()==2){
    impossible();
    return;
  }
  else{
    int ok0=dat[ok[0]][0],
	ok1=dat[ok[1]][0];
    if(question(1,ok0,ok1)==0){//0!=1
      if(question(1,ok0,dat[ok[2]][0])==0){//0!=2
	hone=ok[0];
      }
      else{
	hone=ok[1];
      }
    }
    else{//0==1
      reg(i,2,ok.size()-1){
	int okto=dat[ok[i]][0];
	if(question(1,ok0,okto)==0){//0!=i
	  hone=ok[i];
	  break;
	}
      }
    }
  }
  //printf("hone..%d\n",hone);
  rep(i,dat[hone].size()){
    int no=dat[hone][i];
    answer(no,1);
    gone[no]=1;
  }
  rep(i,N){
    if(gone[i]==0)answer(i,0);
  }
  return;
}

Submission Info

Judge Result