CF1840G1 In Search of Truth (Easy Version) 题解

洛谷题面 | Codeforces 题面 | AC 记录

首先想到的是，如果我询问的 \(k\) 恰巧等于 \(n\)，那么转一圈回来正好指到原来的数字，就能知道答案了。

\[ {\color{red}3},\ 1,\ 4,\ 5,\ 2,\ 6\\ \texttt{+ 6}\\ {\color{red}3},\ 1,\ 4,\ 5,\ 2,\ 6\\ \texttt{! 6} \]

但是这样做显然有一个问题，一旦 \(k\) 不等于 \(n\)，我们不知道现在指向的这个数转完了一圈还是没转完，也就无法确定下一步应该执行什么。

\[ {\color{red}3},\ 1,\ 4,\ 5,\ 2,\ 6\\ \texttt{+ 4}\\ 3,\ 1,\ 4,\ 5,\ {\color{red}2},\ 6 \]

\[ {\color{red}3},\ 1,\ 4,\ 5,\ 2,\ 6\\ \texttt{+ 1145}\\ 3,\ 1,\ 4,\ 5,\ 2,\ {\color{red}6} \]

既然只靠一个数确定位置无法满足我们，那么我们可以确定出来好多好多数的位置。在开始时执行 \(10^3\) 次 + 1 操作，这样我们就知道了前 \(10^3+1\) 个数和它们的位置（都紧挨着）。

如果在询问过程中没有出现重复的数（\(n>10^3\)），那就说明执行的这 \(10^3\) 次操作没有转完一圈。

此时，我们再执行 + 1000 操作直到出现重复的数，并计算答案。此时由于一次转 \(10^3\) 个位置，而我们已经确定了前 \(10^3+1\) 个位置，所以可以保证第一次出现重复的数是只转了一圈出来的结果。

后面这一步最大操作次数约是 \(\frac{10^6-10^3}{10^3} = 999\)，\(10^3 + 999 = 1999\)，小于 \(2023\)，可以通过 Easy Version。

// 珍爱账号，请勿贺题
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr static int N = 1e6 + 11;
int ask(bool d, int h) {
    cout << (d ? '+' : '-') << ' ' << h << endl;
    int x;
    cin >> x;
    return x;
}
void determine(int w) {
    cout << "! " << w << endl;
    exit(0);
}

int a[N], cur, tmp;
void solve() {
    cin >> tmp;
    a[tmp] = cur = 1;
    for (int i = 1; i <= 1000; i++) {
        ++cur;
        tmp = ask(1, 1);
        if (a[tmp]) {
            determine(cur - a[tmp]);
        }
        a[tmp] = cur;
    }
    for (;;) {
        cur += 1000;
        tmp = ask(1, 1000);
        if (a[tmp]) {
            determine(cur - a[tmp]);
        }
        a[tmp] = cur;
    }
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

CF1840G1 In Search of Truth (Easy Version) 题解

评论