Submission #1261761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261761		inkvizytor	Worm Worries (BOI18_worm)	C++20	100 / 100	216 ms	584 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;
        }
        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].second << " 1 1" << endl;
    }

    map<pair<int, int>, int> mp1;

    int f1(int x, int y, int n, int m) {
        if (x<=0||y<=0||x>=n+1||y>=m+1) {
            return 0;
        }
        if (mp1[{x, y}] == 0) {
            cout << "? " << x << ' ' << y << ' ' << 1 << endl;
            int z;
            cin >> z;
            mp1[{x, y}] = z;
        }
        return mp1[{x, y}];
    }

    void solve2(int n, int m, int q) {
        int x1 = 1, y1 = 1, x2 = n, y2 = m;
        while (x1 < x2 || y1 < y2) {
            if (x2-x1>y2-y1) {
                int s = (x1+x2)/2;
                int mk = 0, x = 0, y = 0;
                for (int i = x1-1; i <= x2+2; i++) {
                    if (f1(i, y1-1, n, m) > mk) {
                        mk = f1(i, y1-1, n, m);
                        x = i, y = y1-1;
                    }   
                    if (f1(i, y2+1, n, m) > mk) {
                        mk = f1(i, y2+1, n, m);
                        x = i, y = y2+1;
                    }   
                }
                for (int i = y1-1; i <= y2+1; i++) {
                    if (f1(x1-1, i, n, m) > mk) {
                        mk = f1(x1-1, i, n, m);
                        x = x1-1, y = i;
                    }   
                    if (f1(x2+1, i, n, m) > mk) {
                        mk = f1(x2+1, i, n, m);
                        x = x2+1, y = i;
                    } 
                    if (f1(s, i, n, m) > mk) {
                        mk = f1(s, i, n, m);
                        x = s, y = i;
                    }
                }
                if (x == s) {
                    int a = f1(s-1, y, n, m), b = f1(s+1, y, n, m);
                    if (mk > a && mk > b) {
                        cout << "! " << x << ' ' << y << ' ' << 1 << endl;
                        return;
                    }
                    if (mk < a) {
                        x2 = s-1;
                    }
                    else {
                        x1 = s+1;
                    }
                }
                else {
                    if (x < s) {
                        x2 = s-1;
                    }
                    else {
                        x1 = s+1;
                    }
                }
            }
            else {
                int s = (y1+y2)/2;
                int mk = 0, x = 0, y = 0;
                for (int i = x1-1; i <= x2+1; i++) {
                    if (f1(i, y1-1, n, m) > mk) {
                        mk = f1(i, y1-1, n, m);
                        x = i, y = y1-1;
                    }   
                    if (f1(i, y2+1, n, m) > mk) {
                        mk = f1(i, y2+1, n, m);
                        x = i, y = y2+1;
                    }
                    if (f1(i, s, n, m) > mk) {
                        mk = f1(i, s, n, m);
                        x = i, y = s;
                    }
                }
                for (int i = y1-1; i <= y2+1; i++) {
                    if (f1(x1-1, i, n, m) > mk) {
                        mk = f1(x1-1, i, n, m);
                        x = x1-1, y = i;
                    }   
                    if (f1(x2+1, i, n, m) > mk) {
                        mk = f1(x2+1, i, n, m);
                        x = x2+1, y = i;
                    } 
                }
                if (y == s) {
                    int a = f1(x, s-1, n, m), b = f1(x, s+1, n, m);
                    if (mk > a && mk > b) {
                        cout << "! " << x << ' ' << y << ' ' << 1 << endl;
                        return;
                    }
                    if (mk < a) {
                        y2 = s-1;
                    }
                    else {
                        y1 = s+1;
                    }
                }
                else {
                    if (y < s) {
                        y2 = s-1;
                    }
                    else {
                        y1 = s+1;
                    }
                }
            }
        }
        cout << "! " << x1 << ' ' << y1 << ' ' << 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;
        }
        if (k == 1) {
            solve2(n, m, 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: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23