【Codeforces Round #538 (Div. 2) E. Arithmetic Progression】二分+随机化+交互

E. Arithmetic Progression

题意

现在有一个长度为n的打乱的等差数列，你只知道长度，并且可以提出60个问题，让你确定这个等差序列的首项和公差。问题的格式分为两种:

1:询问等差序列中是否有大于x的数
2:询问等差序列中第i个数是什么

$1\le a_i\le 10^9$
做法

看到这个60，我们肯定知道要想log的算法，由于每个数都小于$10^9$,我们只需要30次就可以算出这个序列的末项是什么。之后的30次提问，我们只需要随机的获取30次下标的值，之后排序取两两相邻差的gcd即可。这个正确性的证明可以看官方题解，$错误率<10^{?9}$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
bool ask(int mid)
{
    printf("> %d\n",mid);fflush(stdout);int x;scanf("%d",&x);return x;
}
std::mt19937 rnd(time(0));
int gcd_(int a, int b)
{
    return b ==0? a : gcd_(b, a % b);
}
int main()
{
    int n;scanf("%d",&n);int l=0,r=1000000000,mid;while(l<=r){
    mid=(l+r)/2;if(ask(mid)) l=mid+1;else r=mid-1;}vector<int> v;for(int i=1;i<=30;i++){
    int tmp=(rnd()%n)+1;printf("? %d\n",tmp);fflush(stdout);int x;scanf("%d",&x);v.push_back(x);}sort(v.begin(),v.end());int gcd=0;for(int i=1;i<v.size();i++){
    gcd=gcd_(gcd,v[i]-v[i-1]);}printf("! %d %d\n",r+1-gcd*(n-1),gcd);fflush(stdout);return 0;
}