POI2013 Where is the one

POI2013 Where is the one

题目大意：

有一个1到n的排列，并且给你两个函数：

f(i,j,d)：返回bool，表示d|(P[i]-P[j])是否成立。

g(i,j):返回P[i]是否比P[j]大.

你可以调用无限次f(只要不TLE)，以及尽量少的g。

最终来确定元素1的位置。

题解：

我们可以发现，f函数可以用来判断，是否存在一个P[j]与P[i]的差值为d。

由于是一个排列，因而满足二分的性质：

以1为基准点，可以二分一个差值，并看看是否存在一个数与P[1]差值为d。

这样可以找到一个与P[1]相差最大的值的位置。(元素1或元素n)

再找到与它相差n-1的元素的位置。(元素1或元素n中的另一个)

最后调用一次g函数判断哪一个更小，那个就是元素1。

（注意特判n=1的情况）

Code：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include "cgdzlib.h"
#include <assert.h>
using namespace std;
int id1,id2;
bool judge(int cur){
	for(int i=2;i<=n;i++)
		if(f(1,i,cur)){id1=i;return true;}
	return false;
}
int main(){
	n=inicjuj();
	if(n==1){
		odpowiedz(1);
		return 0;
	}
	int L=1,R=n-1;
	while(L<=R){
		int mid=L+R>>1;
		if(judge(mid))L=mid+1;
		else R=mid-1;
	}
	for(int i=1;i<=n;i++){
		if(i==id1)continue;
		if(f(id1,i,n-1))id2=i;
	}
	if(g(id1,id2))odpowiedz(id2);
	else odpowiedz(id1);
	return 0;
}