Submission #250929

#	Time	Username	Problem	Language	Result	Execution time	Memory
250929		imeimi2000	Worm Worries (BOI18_worm)	C++17	100 / 100	974 ms	5752 KiB

worm

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int n, m, k, q, a;
int ask(int x = 1, int y = 1, int z = 1) {
    static map<llong, int> mp;
    if (x <= 0) return 0;
    if (y <= 0) return 0;
    if (z <= 0) return 0;
    if (x > n) return 0;
    if (y > m) return 0;
    if (z > k) return 0;
    llong v = x + y * (n + 5ll) + z * (n + 5ll) * (m + 5ll);
    if (mp.find(v) != mp.end()) return mp[v];
    if (q < ++a) exit(1);
    int r;
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    scanf("%d", &r);
    return mp[v] = r;
}
 
void answer(int x = 1, int y = 1, int z = 1) {
    printf("! %d %d %d\n", x, y, z);
    exit(0);
}
 
int gox[6] = { 1, -1, 0, 0, 0, 0 };
int goy[6] = { 0, 0, 1, -1, 0, 0 };
int goz[6] = { 0, 0, 0, 0, 1, -1 };
 
int checkLocalMin(int x = 1, int y = 1, int z = 1) {
    for (int i = 0; i < 6; ++i) {
        if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) return 0;
    }
    return 1;
}
 
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
	if (k > 1) {
        srand(time(0));
        int x = (n + 1) / 2;
        int y = (m + 1) / 2;
        int z = (k + 1) / 2;
        int it = q / 2;
        while (it--) {
            int mx = rand() % n + 1;
            int my = rand() % m + 1;
            int mz = rand() % k + 1;
            if (ask(x, y, z) < ask(mx, my, mz)) x = mx, y = my, z = mz;
        }
        while (1) {
            vector<int> ch = { 0, 1, 2, 3, 4, 5 };
            random_shuffle(ch.begin(), ch.end());
            int c = 0;
            for (int i : ch) {
                if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) {
                    x += gox[i];
                    y += goy[i];
                    z += goz[i];
                    c = 1;
                    break;
                }
            }
            if (c) continue;
            answer(x, y, z);
        }
	}
	else if (m > 1) {
        int sx = 1, ex = n;
        int sy = 1, ey = m;
        int mx = 0, my = 0, mv = 0;
        while (sx < ex || sy < ey) {
            if (ex - sx < ey - sy) {
                int md = (sy + ey) / 2;
                if (md == my) ++md;
                int mxv = 0, mxi = 0;
                for (int i = sx; i <= ex; ++i) {
                    if (mxv < ask(i, md)) mxv = ask(i, md), mxi = i;
                }
                if (mv < mxv) {
                    int l = ask(mxi, md - 1);
                    int r = ask(mxi, md + 1);
                    if (l <= mxv && r <= mxv) answer(mxi, md);
                    mx = mxi;
                    if (l > r) ey = max(md - 1, sy), my = md - 1, mv = l;
                    else sy = min(md + 1, ey), my = md + 1, mv = r;
                }
                else {
                    if (my < md) ey = max(md - 1, sy);
                    else sy = min(md + 1, ey);
                }
            }
            else {
                int md = (sx + ex) / 2;
                if (md == mx) ++md;
                int mxv = 0, mxi = 0;
                for (int i = sy; i <= ey; ++i) {
                    if (mxv < ask(md, i)) mxv = ask(md, i), mxi = i;
                }
                if (mv < mxv) {
                    int l = ask(md - 1, mxi);
                    int r = ask(md + 1, mxi);
                    if (l <= mxv && r <= mxv) answer(md, mxi);
                    my = mxi;
                    if (l > r) ex = max(md - 1, sx), mx = md - 1, mv = l;
                    else sx = min(md + 1, ex), mx = md + 1, mv = r;
                }
                else {
                    if (mx < md) ex = max(md - 1, sx);
                    else sx = min(md + 1, ex);
                }
            }
        }
        answer(mx, my);
	}
	else {
        int s = 1, e = n;
        const double p = 0.382;
        int l = (1 - p) * s + p * e;
        int r = s + e - l;
        while (s < e) {
            if (ask(l) < ask(r)) s = l + 1, l = r, r = max(p * s + (1 - p) * e, l + 1.0);
            else e = r - 1, r = l, l = min((1 - p) * s + p * e, r - 1.0);
        }
        answer(s);
	}
	return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &r);
     ~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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