[POI 20 Stage 3] Where is the one?

作法：

首先可以推出第二種詢問只需要一次就夠了，因為如果暴力枚舉排列中的兩個數，然後用 1 ~ n-1 去試是否整除他，就可以知道哪些數是相差1的，那麼只有一個數和他相差 1 的數就是 1 或 n 了，再問問看這兩個數誰比較大就可以了。所以問題轉化為求出 n 和 1 所在的位置。

因為第一種詢問就等價於問「兩個數是否模 d 同餘」，所以如果我們想求出 1 ~ n 中 1 和 n 的位置，考慮把這些數按照模 2 分成兩坨，如果有一坨的個數比另一坨多，那麼最大和最小數一定在比較多的那坨裡面，否則我們可以分別對兩邊遞回下去，求出最大和最小的數，最後再看看到底哪兩個數才是所求的最大最小數就好了，而這只要拿 n-1 去問兩數是否同餘就好了。具體來說，我們在遞回的時候的子問題是「已知有一些位置的數滿足他們全部都模 d 同餘，且已知最大和最小的差是 m ，要求出最大和最小的數落在哪個位置」，而剛剛考慮的「模 2 分成兩坨」只要改成「模 2 * d 分成兩坨」就好了，並且最後再確認哪兩個數是最大最小數的時候是用 m 去問他們是否同餘。

code :

#include<bits/stdc++.h>
#include"cgdzlib.h"
using namespace std;
const int maxn=500000+10 ;
 
vector<int> v[4*maxn] ;
int vcnt=0 ;
 
void solve(const vector<int> &vec,int d,int m,int &mi,int &ma)
{
    if(vec.size()==2) { mi=vec[0] ; ma=vec[1] ; return ; }
    v[vcnt].push_back(vec[0]) ;
    for(int i=1;i<vec.size();i++)
    {
        if(f(vec[i],vec[0],2*d)) v[vcnt].push_back(vec[i]) ;
        else v[vcnt+1].push_back(vec[i]) ;
    }
    int tmp=vcnt ; vcnt+=2 ;
    if(v[tmp].size()!=v[tmp+1].size())
    {
        if(v[tmp].size()>v[tmp+1].size())
            solve(v[tmp],2*d,m,mi,ma) ;
        else
            solve(v[tmp+1],2*d,m,mi,ma) ;
        return ;
    }
 
    int a[2],b[2] ;
    solve(v[tmp],2*d,m-d,a[0],a[1]) ;
    solve(v[tmp+1],2*d,m-d,b[0],b[1]) ;
    for(int i=0;i<2;i++) for(int j=0;j<2;j++)
        if(f(a[i],b[j],m))
    {
        mi=a[i] ; ma=b[j] ;
        return ;
    }
}
 
main()
{
    int n=inicjuj() ;
    if(n==1) odpowiedz(1) ;
 
    for(int i=1;i<=n;i++) v[0].push_back(i) ;
    vcnt++ ;
    int a,b ;
    solve(v[0],1,n-1,a,b) ;
    if(g(a,b)) odpowiedz(b) ;
    else odpowiedz(a) ;
}