Submission #1261739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261739		inkvizytor	Worm Worries (BOI18_worm)	C++20	49 / 100	216 ms	432 KiB

worm

#include<bits/stdc++.h>
using namespace std;

#define ll long long

unordered_map<int, int> mp;

int f(int x) {
    if (x==0)return 0;
    if (mp[x] == 0) {
        cout << "? " << x << " 1 1" << endl;
        int y;
        cin >> y;
        mp[x] = y;
    }
    return mp[x];
}

double phi = 0.618033988;

void solve1(int n, int q) {
    double p = 1, k = n;
    while((int)round(p) < (int)round(k)-1) {
        double m1 = p*phi+k*((double)1-phi), m2 = p*((double)1-phi)+k*phi;
        int a = f((int)round(m1)), b = f((int)round(m2));
        if (a < b) {
            p = m1;
        }
        else {
            k = m2;
        }
        if ((int)(round(p))==0) p+=1;
        if ((int)(round(k))==n+1) k-=1;
    }
    if (f((int)round(p-1) >= f((int)round(p)))) {
        cout << "! " << (int)round(p-1) << " 1 1" << endl;
    }
    if (f((int)round(p) >= f((int)round(k)))) {
        cout << "! " << (int)round(p) << " 1 1" << endl;
    }
    else {
        cout << "! " << (int)round(k) << " 1 1" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    srand(2137);
    if (m == k && k == 1) {
        solve1(n, q);
        return 0;
    }
    int maks = 0;
    vector<int> p = {0, 0, 0};
    for (int i = 0; i < q/2; i++) {
        int x = rand()%n+1, y = rand()%m+1, z = rand()%k+1;
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        int l;
        cin >> l;
        if (l > maks) {
            maks = l;
            p = {x, y, z};
        }
    }
    for (int i = 0; i < (q/2)/6-7; i++) {
        int s = 0;
        if (p[0]>1) {
            cout << "? " << p[0]-1 << ' ' << p[1] << ' ' << p[2] << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[0]--;
                maks = l;
                s++;
            }
        }
        if (p[0]<n) {
            cout << "? " << p[0]+1 << ' ' << p[1] << ' ' << p[2] << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[0]++;
                maks = l;
                s++;
            }
        }
        if (p[1]>1) {
            cout << "? " << p[0] << ' ' << p[1]-1 << ' ' << p[2] << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[1]--;
                maks = l;
                s++;
            }
        }
        if (p[1]<m) {
            cout << "? " << p[0] << ' ' << p[1]+1 << ' ' << p[2] << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[1]++;
                maks = l;
                s++;
            }
        }
        if (p[2]>1) {
            cout << "? " << p[0] << ' ' << p[1] << ' ' << p[2]-1 << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[2]--;
                maks = l;
                s++;
            }
        }
        if (p[2]<k) {
            cout << "? " << p[0] << ' ' << p[1] << ' ' << p[2]+1 << endl;
            int l;
            cin >> l;
            if (l > maks) {
                p[2]++;
                maks = l;
                s++;
            }
        }
        if (s == 0) {
            break;
        }
    }
    cout << "! " << p[0] << ' ' << p[1] << ' ' << p[2] << endl;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23