Submission #1218713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218713		qwerasdfzxcl	Worm Worries (BOI18_worm)	C++20	58 / 100	290 ms	6440 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){

}

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 (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:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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