Submission #542615

#	Time	Username	Problem	Language	Result	Execution time	Memory
542615		OttoTheDino	Worm Worries (BOI18_worm)	C++17	0 / 100	724 ms	1048576 KiB

worm

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

vi d6[6] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int save[(int)1e6+1] = {}, ans = -1; 
double φ = 1.618;

int qry (int z, int y, int x) {
    if (y==1 && z==1 && save[x]) return save[x];
    cout << "? " << x << " " << y << " " << z << endl;
    int res; cin >> res;
    if (z==1 && y==1) save[x] = res;
    return res;
}

int rand (int a, int b) {
    return a + rand() % (b-a+1);
}

void guess (int x) {
    bool suc = 1;
    if (x>1 && qry(1,1,x-1)>qry(1,1,x)) suc = 0;
    if (x<1e6 && qry(1,1,x+1)>qry(1,1,x)) suc = 0;
    if (suc) {
        ans = x;
    }

}

void solve (int a, int b, int c, int d) {
    if (c-a==2) {
        guess(a),guess(b),guess(c);
        return;
    }
    int l = c-a+1;
    if (d) {
        int nw = a+l*φ/(2*φ+1);
        qry (1,1,nw);
        if (save[a]>=save[nw]) solve (a,nw,b,1);
        if (save[nw]>=save[a] && save[nw]>=save[b]) solve (a, nw, b,1);
        if (save[b]>=save[nw] && save[b]>=save[c]) solve(nw,b,c,0);
    }
    else {
        int nw = a+l*(1-φ/(2*φ+1));
        qry (1,1,nw);
        if (save[a]>=save[b]) solve (a, b, nw, 1);
        else if (save[b]>=save[a] && save[b]>=save[nw]) solve (a, b, nw, 1);
        else solve(b,nw,c,0);
    }
}

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

    srand(128);

    int n, m, k, q; cin >> n >> m >> k >> q;

    swap(n,m);
    swap(m,k);
    swap(k,q);
    swap(n,m);
    swap(m,k);
    swap(n,m);

    if (n>1 && m>1) {
        int best = 0, a = 0, b = 0, c = 0;
        rep (i,1,q/2) {
            int x = rand(1,n), y = rand(1,m), z = rand(1,k);
            int res = qry (x, y, z);
            if (res>best) {
                best = res;
                a = x, b = y, c = z;
            }
        }
        int cnt = 0;
        while (true) {
            bool hap = 0;
            rep (i,0,5) {
                int na = a + d6[i][0];
                int nb = b + d6[i][1];
                int nc = c + d6[i][2];
                int res = qry (na, nb, nc);
                if (++cnt>q/2) {
                    cout << "! " << a << " " << b << " " << c << endl;
                    return 0;
                }
                if (res > best) {
                    best = res;
                    hap = 1;
                    a = na;
                    b = nb;
                    c = nc;
                    break;
                }
            }
            if (!hap) {
                cout << "! " << c  << " "<< b << " " << a << endl;
                break;
            }
        }
    }
    else if (n==1) {
        cout << "! 1 1 1" << endl;
    }
    else {
        qry(1,1,1);
        qry(1,1,n);
        qry(1,1,1+n*φ/(2*φ+1));
        solve(1,1+n*φ/(2*φ+1),n,0);
        cout << "! " <<  ans << " 1 1" << endl;
    }

    return 0;
}

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