有谁愿意帮我这个傻逼看看 D 吗

irris @ 2022-08-07 00:35:15

int query(int a, int b) {
    printf("? %d %d\n", a, b);
    fflush(stdout);
    static int ans;
    ans = read<int>();
    if (ans == -1) exit(0);
    return ans;
}

int find_max(int a, int b, int c, int d) {
    int p = query(a, c);
    if (p == 1) 
        return query(a, d) == 1 ? a : d;
    if (p == 0) 
        return query(b, d) == 1 ? b : d;
    if (p == 2) 
        return query(c, b) == 1 ? c : b;
    exit(-1);
}

void solve() {
    int N = read<int>();
    if (N == -1) exit(0);
    if (N == 1) {
        printf("! %d\n", query(1, 2));
        fflush(stdout);
        return;
    }
    std::queue<int> p;
    for (int i = 1; i <= (1 << N); ++i) p.push(i);
    if (N % 2 == 1) {
        int t = 1 << (N - 1);
        while (t--) {
            int a = p.front(); p.pop();
            int b = p.front(); p.pop();
            p.push(query(a, b) == 1 ? a : b);
        }
    }
    while (p.size() != 1) {
        int t = (int)p.size() / 4;
        while (t--) {
            int a = p.front(); p.pop();
            int b = p.front(); p.pop();
            int c = p.front(); p.pop();
            int d = p.front(); p.pop();
            p.push(find_max(a, b, c, d));
        }
    }
    printf("! %d\n", p.front());
    fflush(stdout);
}

int main() {
    int T = read<int>();
    while (T--) solve();
    return 0;
}

by fast_photon @ 2022-08-07 00:37:48

借楼同问，WA 2

#include<cmath>
#include<cstdio> 
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define int long long
#define maxn 25

using namespace std;

int T, n, lst;
vector<int> g[25];

signed main() {
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 0; i <= n; i++) {
            g[i].clear();
            g[i].push_back(-1);
        }
        for(int i = 1; i <= (1 << n); i++) {
            g[0].push_back(i);
        }
        for(int j = 1; j < n; j++) {
            for(int i = 1; i <= (1 << (n - j + 1)); i += 4) {
                cout << "? " << g[j - 1][i] << ' ' << g[j - 1][i + 2] << endl;
                fflush(stdout);
                int res;
                cin >> res;
                if(res == 0) g[j].push_back(g[j - 1][i + 1]), g[j].push_back(g[j - 1][i + 3]);
                else if(res == 1) g[j].push_back(g[j - 1][i]), g[j].push_back(g[j - 1][i + 3]);
                else g[j].push_back(g[j - 1][i + 1]), g[j].push_back(g[j - 1][i + 2]);
            }
        }
        cout << "? " << g[n - 1][1] << ' ' << g[n - 1][2] << endl;
        fflush(stdout);
        int res;
        cin >> res;
        cout << "! ";
        if(res == 1) {
            cout << g[n - 1][1] << endl;
        }
        else cout << g[n - 1][2] << endl;
        fflush(stdout);
    }
} 

by irris @ 2022-08-07 00:38:30

@fast_photon 啊我们四人组的想法应该是类似的，但是你这个很难不保证出 bug

by derta @ 2022-08-07 00:49:35

@AlgorithmerSnow N%2==1 时暴力判次数炸了吧

by irris @ 2022-08-07 00:50:27

@derta 没有吧，至少 N = 3 没炸，而且我没有 OLE /kel

by irris @ 2022-08-07 00:51:27

1515151515哥们在这给你调交互

by derta @ 2022-08-07 00:51:42

@AlgorithmerSnow 那个，次数过多好像是返回 WA。

by CreutzWilknare @ 2022-08-07 00:52:41

1 5 用 26 下，限制是 22 下

by irris @ 2022-08-07 00:52:56

那我再看看题面，可是我这上不了 CF 了！！！1

by CreutzWilknare @ 2022-08-07 00:53:25

你 %2=1 判断丢到最后啊，最后剩两个的时候做一下

by CreutzWilknare @ 2022-08-07 00:53:48

这个操作是亏的，信息熵不够，你前面一下做那么多不寄了