[TIOJ] 1945. 小向的試煉 1-1：猜謎遊戲(Guessing)

題目連結:http://tioj.infor.org/problems/1945

---

這題看到他詢問的次數後，應該很容易想到我們的上限就是$N+\log_2 N+2$，那那$N$必定是先單點詢問一遍，然後$\log_2 N$就是二分搜誰說謊，值得注意的是，你發現右半塊沒問題後不能又去問左半塊，要直接問左半塊的小孩，不然Query的次數會變成$2 \times N$，如果要確認會不會CE之類的話或詢問太多次，可以複製我下面的標頭檔，大概這樣吧

#include <cstdio>
#define N 131072
#include "lib1945.h"

int q[N+5]; 
int arr[N+5];

int sum[N+5];

inline int query(int l,int r){
	return (l==0)?sum[r-1]&1:(sum[r-1]-sum[l-1])&1;
}

inline void check(int l, int r){
	if(r-l==1){
		int k = Query(1,q+l);
		if(k!=query(l,l+1))
			arr[l]=Query(1,q+l);
	}else{
		int m=(l+r)/2;
		int fromXian = Query(m-l, q+l);
		int fromOrigin = query(l,m);
		if(fromOrigin == fromXian)
			check(m,r);
		else
			check(l,m);
	}
	
}

int main(){
	Init();
	for(int i=0;i<N;i++)
		q[i]=i;
	for(int i=0;i<N;i++)
		arr[i]=Query(1,q+i);
	sum[0]=arr[0];
	for(int i=1;i<N;i++)
		sum[i] = sum[i-1]+arr[i];
	check(0,N);
	for(int i=0;i<N;i++)
		printf("%d ",arr[i]);
	return 0;
}

附上我自己在用的lib1945.h

#include <cstdio>
#include <cstdlib>
#include <ctime>
#define __N__ 131072
int __arr__[__N__];
bool __ttff__=0;
int __C__=0;

void Init(){
	srand(time(NULL));
	for(int i=0;i<__N__;i++)
		__arr__[i]=rand()%2;
}

int Query(int n,int a[]){
	int count=0;
	for(int i=0;i<n;i++)
		count+=__arr__[a[i]];
	if(!__ttff__&&rand()%50==1){
		__ttff__=1;
		return (count+1)%2;
	}
	//printf("C:%d\n",++__C__);
	return count%2;
}