P8052 [ZYOI Round1] Truth/真心话大冒险 题解

· · 题解

做题背景：期末考试复习，下午有两节自习。我和长老 @Yeegle 趁自习用班上的希沃一体机打题，代码都是在你谷 IDE 里用屏幕键盘一点一点码的，就这还能切两道，离谱。

屏幕键盘的效率相当低下，所以长老为了压缩码量想出了 “ 用 cmp 魔改 sort 实现全自动交互 ” 的思路，在此表示膜拜及感谢。

思路

官方的做法是分类讨论 + 归并排序，码量对于两个一体机 OIer 而言相当 EX 。当然复杂度还是很优秀的，“ 带巨大常数 ” 系 fAKe 言论。

我们考虑题目中操作的实际意义，或者用文化课老师的话来说，就是：揣测出题人的意图。

首先看到操作 1 ， “ 给 3 个数，得知其中排名中间的那个 ” ，乍看之下毫无头绪，既不能暴力一个一个比，也不能像 RMQ 那样得知区间的最大。

然后看到操作 2 ，这个操作不仅有 “ 2 个数中必须有一个排名第一 ” 的限制，而且只能得知谁排名第一，可我怎么保证我进行这个操作时，两个数里一定有一个排名第一呢？

…… 也就是说这个排名第一 一定可以只靠操作 1 得到？假如我做无数次操作 1 ，会发生什么？

一定会有两个数绝对不会出现在操作 1 的回答中，这就是排名第一和排名最后。 因为 排名第一 和 排名最后 无法靠后 / 靠前于任何一个人，自己也不行。

那我们只要做 n-2 次操作就可以得到这两个人：用一个队列存下所有人的序号，每次从队首取 3 个序号出来并将其出队，对这 3 个序号执行操作 1 。然后将除回答得到的序号外的 2 个序号重新入队。

由于每次操作都会出队一个序号，在 n-2 次操作后队列中就只剩下 2 个序号了，这就是排名最前和排名最后的序号。

接下来取出这两个序号，执行操作 2 ，就得到了排名第一。如此，操作 2 物尽其用。

接下来，我们已经知道了排名第一是谁，然后呢？

注意到 3 个数中排名最前已经确定时， “ 回答 3 个数中中间那个 ” 就是 “回答剩下 2 个数中排名靠前那个。”那么我们就可以利用排名第一执行操作 1 ，这样回答的就是剩下两个数中排名靠前那个。

……那不就是一个赤裸裸的比较函数吗。

借助这个性质，我们可以将其写成 cmp ，利用工具人 sort 同学进行 “ 全自动交互 ” ，从而节省不少码量。起码对于两个一体机打题人而言足够了

细节见代码。

代码

#include<bits/stdc++.h>
#define ll long long
#define R read()
using namespace std;
inline ll read() {
    ll s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
inline void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10),x%=10;
    putchar('0'+x);
}//Don't use it for CF.
inline void wk(ll x){write(x);putchar(' ');}
inline void we(ll x){write(x);putchar('\n');}
ll n,a[20005]; 
ll i,j,k,b;// b 为通过第一轮操作 1 得出的最受喜爱，其余为工具变量。 
ll x[3];//第一轮操作 1 最后一步所用工具变量 
queue<ll> q;
bool cmp(ll l,ll r){//第二轮操作 1, 通过魔改cmp实现sort全自动交互（不是） 
    wk(1),wk(b),wk(l),we(r);//输出1,b,l,r。由于b已知最受喜爱，因此回答必为l,r中更受喜爱的那个。 
    fflush(stdout);
    i=R;
    return i==l?1:0;
}
int main(){
    n=R;
    for(i=0;i<n;i++)q.push(i+1);//将所有人入队，一会挨个踢出来 

    for(i=0;i<n-2;i++){
        wk(1);//第一轮操作 1 ，此阶段通过操作 1 将所有人筛得只剩最喜欢的和最不喜欢的。 
        for(j=0;j<3;j++){
            wk(x[j]=q.front());
            q.pop();
        }
        fflush(stdout);
        k=R;
        for(j=0;j<3;j++)if(x[j]!=k)q.push(x[j]);//将未被输出的重新入队。这样一来一定会剩两个从未被输出的，这就是最大和最小。 
    }
    x[0]=q.front();
    q.pop();
    x[1]=q.front();
    q.pop();//把最大最小拎出来 
    wk(2),wk(x[0]),wk(x[1]);//操作 2 ，揪出最喜欢的 
    fflush(stdout);
    b=R;//这样 b 就是最喜欢的了，然后拿去给 cmp 当工具人。 
    for(i=j=0;i<n;i++)if(i!=b-1)a[j++]=i+1;
    sort(a,a+n-1,cmp);//排序 ·魔改 ver
    //这样用这种画风清奇的快排，就可以轻松地用操作 1 来当做大小比较，从而得到排列。 
    wk(3),wk(b);//先把最喜欢的输了 
    for(i=0;i<n-1;i++)wk(a[i]);//依次输出 
    fflush(stdout);
    return 0;
}

坑点：记得 

fflush(stdout);

劲 爆 交 互

超 长 输 出

评 测 特 性

当 场 超 时