Submission #1261747

#TimeUsernameProblemLanguageResultExecution timeMemory
1261747inkvizytorWorm Worries (BOI18_worm)C++20
49 / 100
220 ms432 KiB
#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;
    }
    vector<pair<int, int>> x;
    x.push_back({f((int)round(p-1)), (int)round(p-1)});
    x.push_back({f((int)round(p)), (int)round(p)});
    x.push_back({f((int)round(k)), (int)round(k)});
    if (k < n)x.push_back({f((int)round(k+1)), (int)round(k+1)});
    sort(x.begin(), x.end(), greater<pair<int, int>>());
    cout << "! " << x[0].first << " 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...