Submission #578724

#	Time	Username	Problem	Language	Result	Execution time	Memory
578724		Jarif_Rahman	Worm Worries (BOI18_worm)	C++17	81 / 100	913 ms	288 KiB

worm

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef long double ld;

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

int next(int a, int b){
    return uniform_int_distribution(a, b)(rng);
}

int n, m, k, q;

int query(int x = 1, int y = 1, int z = 1){
    if(x < 1 || x > n || y < 1 || y > m || z < 1 || z > k) return 0;
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    int rt;
    scanf("%d", &rt);
    return rt;
}

const ld rat = (ld(3)-sqrt(ld(5)))/2.0;

void solve1d(){
    int l = 1, r = n;
    int p = ld(n)*rat;
    p = max(1, p);
    int ls = query(p);
    bool rev = 0;

    bool brute = 0;

    while(1){
        if(brute || int(ld(r-l+1)*rat) == 1){
            int mx = 0, ans = -1;
            for(int i = l; i <= r; i++){
                int x = query(i);
                if(x > mx) mx = x, ans = i;
            }
            printf("! %d 1 1\n", ans);
            fflush(stdout);
            exit(0);
        }
        if(!rev){
            int x = r-int(ld(r-l+1)*rat)+1;
            if(x <= p){ brute = 1; continue; }
            int X = query(x);
            if(X <= ls) r = x, rev = 1;
            else l = p, p = x, ls = X;
        }
        else{
            int x = l+int(ld(r-l+1)*rat)-1;
            if(x >= p){ brute = 1; continue; }
            int X = query(x);
            if(X <= ls) l = x, rev = 0;
            else r = p, p = x, ls = X;
        }
    }
}

void solve3d(){
    int mx = 0, a = 1, b = 1, c = 1;

    for(int i = 0; i < q/2; i++){
        int x = next(1, n), y = next(1, m), z = next(1, k);
        int cur = query(x, y, z);
        if(cur > mx) mx = cur, a = x, b = y, c = z;
    }

    while(1){
        int _mx = 0;
        int x, y, z, cur;

        cur = query(a+1, b, c);
        if(cur > _mx) _mx = cur, x = a+1, y = b, z = c;
        cur = query(a-1, b, c);
        if(cur > _mx) _mx = cur, x = a-1, y = b, z = c;
        cur = query(a, b+1, c);
        if(cur > _mx) _mx = cur, x = a, y = b+1, z = c;
        cur = query(a, b-1, c);
        if(cur > _mx) _mx = cur, x = a, y = b-1, z = c;
        cur = query(a, b, c+1);
        if(cur > _mx) _mx = cur, x = a, y = b, z = c+1;
        cur = query(a, b, c-1);
        if(cur > _mx) _mx = cur, x = a, y = b, z = c-1;

        if(_mx <= mx){
            printf("! %d %d %d\n", a, b, c);
            fflush(stdout);
            exit(0);
        }
        else{
            a = x, b = y, c = z, mx = _mx;
        }
    }
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &q);

    if(m == 1 && k == 1) solve1d();
    else solve3d();
}

Compilation message (stderr)

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