CodeForces

Luogu

分析

首先二分出最大的数，可以通过至多$31$次询问得到。

然后，随机询问一些位置的数，然后将所有得到的数排个序，取差的$\gcd$，就能得到公差。

正确率好像非常高，详见官方题解。

需要注意的是，CF是$\mathrm{Windows}$评测机，所以rand()要写成(rand()<<15|rand())。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

int vis[4000010],a[50],s=0;

int main() {
    srand(19260817);
    int n; cin>>n;
    int L=0,R=1e9;
    while (L<R) {
        int mid=(L+R)>>1;
        cout<<"> "<<mid<<endl; fflush(stdout);
        int x; cin>>x;
        if (x) L=mid+1;
        else R=mid;
    }
    cout<<"> "<<L<<endl; fflush(stdout);
    int x; cin>>x; if (!x) --L;
    for (re int i=1;i<=min(29,n);++i) {
        int x=(rand()<<15|rand())%n+1;
        while (vis[x]) x=(rand()<<15|rand())%n+1;
        vis[x]=1;
        cout<<"? "<<x<<endl; fflush(stdout);
        cin>>a[++s];
    }
    sort(a+1,a+s+1); int d=a[2]-a[1];
    for (re int i=3;i<=s;++i) d=__gcd(d,a[i]-a[i-1]);
    cout<<"! "<<L-(n-1)*d+1<<" "<<d<<endl; fflush(stdout);
    return 0;
}