Submission #1218717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218717		qwerasdfzxcl	Worm Worries (BOI18_worm)	C++20	100 / 100	302 ms	6720 KiB

worm

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

map<array<int, 3>, int> mp;

int query(int x, int y, int z){
    if (mp.find(array<int, 3>{x, y, z}) != mp.end()) return mp[{x, y, z}];
    printf("? %d %d %d\n", x, y, z); fflush(stdout);
    
    int ret;
    scanf("%d", &ret);

    return mp[{x, y, z}] = ret;
}

void answer(int x, int y, int z){
    printf("! %d %d %d\n", x, y, z); fflush(stdout);
    exit(0);
}

void solve5(int n, int m, int k, int q){
    auto queryX = [&](int x){
        int ret = -1;
        for (int i=1;i<=m;i++) for (int j=1;j<=k;j++) ret = max(ret, query(x, i, j));
        return ret;
    };
    
    int l = 1, r = n, piv[2] = {-1, -1};
    
    while(l<r){
        int pos[2];
        pos[0] = (double)(r-l+1) * (3-sqrt(5)) / 2;
        pos[1] = r-l-pos[0];
        if (pos[0]==pos[1]) pos[0]--, pos[1]++;
        pos[0] += l, pos[1] += l;

        // printf(" l = %d r = %d\n", l, r);

        if (piv[0]==-1 && piv[1]==-1){
            piv[0] = pos[0];
            piv[1] = pos[1];
        }

        else if (piv[0]==-1){
            piv[0] = pos[0];
        }

        else{
            piv[1] = pos[1];
        }

        if (piv[0] >= piv[1]){
            swap(piv[0], piv[1]);
            if (piv[0]==piv[1]){
                if (piv[0] > pos[0]) piv[0]--;
                else piv[1]++;
            }
        }

        if (queryX(piv[0]) >= queryX(piv[1])){
            r = piv[1]-1;
            piv[1] = piv[0];
            piv[0] = -1;
        }

        else{
            l = piv[0]+1;
            piv[0] = piv[1];
            piv[1] = -1;
        }
    }

    int val = queryX(l);
    for (int i=1;i<=m;i++) for (int j=1;j<=k;j++) if (val==query(l, i, j)) answer(l, i, j);
}

void solve4(int n, int m, int k, int q){
    int lx = 1, rx = n, ly = 1, ry = m, cx = -1, cy = -1;

    while(lx < rx || ly < ry){
        if (rx-lx >= ry-ly){
            int midx = (lx + rx) / 2;
            int mx = -1, opt = -1;
            for (int j=ly;j<=ry;j++) if (mx < query(midx, j, 1)) mx = query(midx, j, 1), opt = j;

            if (cx!=-1 && query(cx, cy, 1) > mx){
                if (cx < midx) rx = midx-1;
                else lx = midx+1;
                continue;
            }

            int flag = 0;
            for (int t=-1;t<=1;t+=2){
                int nx = midx + t, ny = opt;
                if (nx < lx || nx > rx) continue;
                if (ny < ly || ny > ry) continue;

                if (query(nx, ny, 1) > mx){
                    if (t==-1) rx = midx-1;
                    else lx = midx+1;
                    flag = 1, cx = nx, cy = ny;
                    break;
                }
            }

            if (!flag) answer(midx, opt, 1);
        }

        else{
            int midy = (ly + ry) / 2;
            int mx = -1, opt = -1;
            for (int i=lx;i<=rx;i++) if (mx < query(i, midy, 1)) mx = query(i, midy, 1), opt = i;

            if (cy!=-1 && query(cx, cy, 1) > mx){
                if (cy < midy) ry = midy-1;
                else ly = midy+1;
                continue;
            }

            int flag = 0;
            for (int t=-1;t<=1;t+=2){
                int nx = opt, ny = midy + t;
                if (nx < lx || nx > rx) continue;
                if (ny < ly || ny > ry) continue;

                if (query(nx, ny, 1) > mx){
                    if (t==-1) ry = midy-1;
                    else ly = midy+1;
                    flag = 1, cx = nx, cy = ny;
                    break;
                }
            }

            if (!flag) answer(opt, midy, 1);
        }
    }

    answer(lx, ly, 1);
}

void solve6(int n, int m, int k, int q){
    static int dx[6] = {1, -1, 0, 0, 0, 0};
    static int dy[6] = {0, 0, 1, -1, 0, 0};
    static int dz[6] = {0, 0, 0, 0, 1, -1};

    mt19937 seed(1557);
    uniform_int_distribution<int> rng(1, n);

    int mx = -1;
    array<int, 3> opt = {-1, -1, -1};

    for (int i=1;i<=q/2;i++){
        array<int, 3> p = {rng(seed), rng(seed), rng(seed)};
        int val = query(p[0], p[1], p[2]);
        if (val > mx) mx = val, opt = p;
    }

    while(true){
        auto [cx, cy, cz] = opt;
        int flag = 0;

        for (int i=0;i<6;i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            int nz = cz + dz[i];

            if (nx < 1 || nx > n) continue;
            if (ny < 1 || ny > n) continue;
            if (nz < 1 || nz > n) continue;

            if (query(nx, ny, nz) > query(cx, cy, cz)){
                opt = {nx, ny, nz};
                flag = 1;
                break;
            }
        }

        if (!flag) answer(cx, cy, cz);
    }
}

int main(){
    int n, m, k, q;
    scanf("%d %d %d %d", &n, &m, &k, &q);
    if (n==1000 && m==1000) solve4(n, m, k, q);
    else if (n==500 && m==500 && k==500) solve6(n, m, k, q);
    else solve5(n, m, k, q);
}

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", &ret);
      |     ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:186:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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