Submission #723730

#	Time	Username	Problem	Language	Result	Execution time	Memory
723730		dxz05	Worm Worries (BOI18_worm)	C++17	10 / 100	1060 ms	9748 KiB

worm

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int queries = 0;
int query(int x, int y, int z) {
    queries++;

	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	int ans = -1;

#ifdef LOCAL
    ans = rng() % 1000000 + 1;
#else
    (void)scanf("%d", &ans);
#endif

	if (ans == -1) exit(0);
	return ans;
}

__attribute__((noreturn))
void guess(int x, int y, int z) {
	printf("! %d %d %d\n", x, y, z);
	exit(0);
}

typedef long long ll;

int N, M, K;

map<ll, int> mp;
int ask(int x, int y, int z){
    if (x < 1 || x > N) return 0;
    if (y < 1 || y > M) return 0;
    if (z < 1 || z > K) return 0;

    ll val = x * 2'000'010'000'100LL + y * 1'000'002LL + z;
    if (mp.find(val) != mp.end()) return mp[val];
    return mp[val] = query(x, y, z);
}

void check(int x, int y, int z){
    if (ask(x, y, z) < ask(x - 1, y, z)) return;
    if (ask(x, y, z) < ask(x + 1, y, z)) return;
    if (ask(x, y, z) < ask(x, y - 1, z)) return;
    if (ask(x, y, z) < ask(x, y + 1, z)) return;
    if (ask(x, y, z) < ask(x, y, z - 1)) return;
    if (ask(x, y, z) < ask(x, y, z + 1)) return;

    cerr << "Queries made " << queries << endl;

    guess(x, y, z);
}

int main() {
	int Q;
	(void)scanf("%d %d %d %d", &N, &M, &K, &Q);

    for (int y = 1; y <= M; y++) {
        for (int z = 1; z <= K; z++) {
            int l = 1, r = N;

            while (l < r) {
                int mid = l + rng() % (r - l + 1);
                int val1 = ask(mid, y, z), val2 = ask(mid + 1, y, z);

                if (val1 >= val2) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            check(l, y, z);
        }
    }

}

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:20:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     (void)scanf("%d", &ans);
      |           ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:63:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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