CF 1114 E. Arithmetic Progression

E. Arithmetic Progression

链接

题意：

　　交互题。

　　有一个等差序列，现已打乱顺序，最多询问60次来确定首项和公差。每次可以询问是否有严格大于x的数，和查看一个位置的数。

分析：

　　首先可以二分找到序列的最大值，然后考虑如何求公差。

　　随机选30个数，然后对任意两个求一遍gcd即可。

　　正确性证明

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int query(int ty,LL x) {

    int y;

    if (ty == ) printf("> %I64d\n", x);

    else printf("? %I64d\n", x);

    fflush(stdout);

    cin >> y;

    if (y == -) exit();

    return y;

}

vector<LL> vec;

int Rand() { return (rand() << ) | rand(); }

int id[];

int main() {

    srand();

    int n; cin >> n;

    LL l = -1e9, r = 1e9, ans = , cnt = , tot = n;

    while (l <= r) {

        LL mid = (l + r) >> ;

        cnt --;

        if (query(, mid) == ) ans = mid, r = mid - ;

        else l = mid + ;

    }

    for (int i = ; i <= tot; ++i) id[i] = i;

    while (cnt >  && tot > ) {

        int x = Rand() % tot + ;

        vec.push_back(query(, id[x]));

        swap(id[x], id[tot]);

        tot --;    cnt --;

    }

    sort(vec.begin(), vec.end());

    if (vec.back() != ans) vec.push_back(ans);

    LL d = vec[] - vec[];

    for (int i = ; i < (int)vec.size() - ; ++i) d = __gcd(d, vec[i + ] - vec[i]);

    printf("! %I64d %I64d\n", ans - (n - ) * d, d);

    return ;

}