Submission #724252

#	Time	Username	Problem	Language	Result	Execution time	Memory
724252		drdilyor	Worm Worries (BOI18_worm)	C++17	0 / 100	3 ms	4176 KiB

worm

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

int arr[100];
int query(int x, int y, int z) {
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
#ifdef ONPC
    return arr[x];
#endif
	int ans = -1;
	(void)scanf("%d", &ans);
	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);
#ifdef ONPC
    printf("[%d %d %d]", arr[x-1], arr[x], arr[x+1]);
    fflush(stdout);
    if (!(arr[x-1] <= arr[x] && arr[x] >= arr[x+1])) {
        for (int i = 1; i <= 15 ;i++)
            cout << arr[i] << ' ';
        cout << endl;
        assert(false);
    }
#endif
	exit(0);
}



int main() {
    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	int N, M, K, Q;
	(void)scanf("%d %d %d %d", &N, &M, &K, &Q);
    assert(M == 1 && K == 1);
#ifdef ONPC
    for (int i = 1; i <= N; i++)
        arr[i] = rng() % 10;
#endif
    vector<int> cache(N+1);
    auto ask = [&](int x) {
        if (cache[x]) return cache[x];
        return cache[x] = query(x, 1, 1);
    };
    if (N == 1) {
        guess(1, 1, 1);
    }

    double phi = (sqrt(5.0) + 1) / 2;
    double eps = 1e-5;
    double l = 1, r = N;
    while (r - l >= 4-eps) {
        double a = r - (r - l) / phi;
        double b = l + (r - l) / phi;
        int ar = round(a)+eps;
        int br = round(b)+eps;
        if (ar == int(round(l)+eps)) ar++;
        if (br == int(round(r)+eps)) br--;
        if (ask(ar) <= ask(br)) {
            l = a;
        } else r = b;
    }
    int ll = round(l) + eps;
    int rr = round(r) + eps;
    for (int i : {ll, ll+1, rr-1, rr})
        if (ask(i) >= (i >= N ? 0 : ask(i+1)) && ask(i) >= (i <= 1 ? 0 : ask(i-1)))
            guess(i, 1, 1);
}

Compilation message (stderr)

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

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