资讯详情

「MCOI-07」Dream and More Discs

首先考虑对于一个 \(x\)，\(\leq x\) 的数构成什么结构：

对于所有红线左边的数，均 \(\leq x\)，考虑我们只需要得到这些红线即可。

对于每个位置，初始时红线的可选区间为 \([0,2^m-1]\)，接下来需要将红线的可选区间缩短。

这里我们采用二分的手法，考虑当前得到了红线为 \(mid\) 位置如下：

红线左边数的个数为 \(t=m_1+m_2+m_3+m_4\)，且假设 \(x_1<x_2<x_3<x_4\)。

显然，\(x_4\) 的排名不低于 \(t\)，\(x_1\) 的排名不高于 \(t-n+1\)。

首先考虑当 \(k \leq t\) 时，\(x_4\) 的排名必然 \(\geq k\)，令 \(r_4 = m_4\)。

若 \(k > t-n+1\)，\(x_1\) 的排名必然 \(< k\)，令 \(l_1 = m_1 + 1\)。

显然两个条件必将满足至少一个，如此操作直到所有 \(l_i=r_i\) 即可。

然而这样会在已经存在某些 \(l_i=r_i\) 时出问题，我们需要忽略这些部分。

考虑当前对于 \(x_{\max}\) 的排名下界要减去 \(l_i=r_i\) 中 \(x > x_{\max}\) 的部分。

同时 \(x_{\min}\) 的排名上界要加上 \(l_i=r_i\) 中 \(x < x_{\min}\) 的部分。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,Th;
long long a[60][1<<11];
int l[60],r[60],mid[60];
long long query(int id,int pos){if(a[id][pos]==0){cout<<"? "<<id<<" "<<pos<<endl;cin>>a[id][pos];}return a[id][pos];
}
struct Node{int pos;long long num;
}op[60];
bool operator <(const Node &lhs,const Node &rhs){return lhs.num<rhs.num;
} 
int main(){cin>>n>>m>>k>>Th;for(int i=1;i<=n;i++){a[i][0]=-1;l[i]=0;r[i]=(1<<m)-1;}while(true){int tot=0,sum=0;for(int i=1;i<=n;i++){mid[i]=(l[i]+r[i])>>1;sum+=mid[i];if(l[i]!=r[i]){op[++tot]=(Node){i,query(i,mid[i])};}}if(tot==0){break;}sort(op+1,op+tot+1);int tot_bigger=0;for(int i=1;i<=n;i++){if(l[i]==r[i]){if(query(i,l[i])>op[tot].num){tot_bigger++;}}}if(k<=sum-tot_bigger){r[op[tot].pos]=mid[op[tot].pos];}else{l[op[1].pos]=mid[op[1].pos]+1;}}int tot=0;for(int i=1;i<=n;i++){tot+=l[i];}while(tot>=k){int id=1;for(int i=2;i<=n;i++){if(query(i,l[i])>query(id,l[id])){id=i;}}if(tot==k){cout<<"! "<<id<<" "<<l[id]<<endl;return 0; }else{l[id]--;tot--;}}return 0;
}