Submission #579019

#TimeUsernameProblemLanguageResultExecution timeMemory
579019Jarif_RahmanWorm Worries (BOI18_worm)C++17
100 / 100
740 ms280 KiB
#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 solve2d(){
    int l1 = 1, r1 = n, l2 = 1, r2 = m;
    bool vert = 1;

    pair<int, int> lsp = {-1, -1};
    int ls = 0;

    while(1){
        if(vert){
            int md = (l2+r2)/2;
            int mx = 0, in = -1;
            for(int i = l1; i <= r1; i++){
                int x = query(i, md);
                if(x > mx) mx = x, in = i;
            }

            if(ls > mx){
                if(lsp.sc < md) r2 = md-1;
                else l2 = md+1;
                vert = 0;
                continue;
            }

            int a = query(in, md-1), b = query(in, md+1);

            if(max(a, b) <= mx){
                printf("! %d %d 1\n", in, md);
                fflush(stdout);
                exit(0);
            }
            else if(a > b) r2 = md-1, ls = a, lsp = {in, md-1};
            else l2 = md+1, ls = b, lsp = {in, md+1};
            vert = 0;
        }
        else{
            int md = (l1+r1)/2;
            int mx = 0, in = -1;
            for(int i = l2; i <= r2; i++){
                int x = query(md, i);
                if(x > mx) mx = x, in = i;
            }

            if(ls > mx){
                if(lsp.f < md) r1 = md-1;
                else l1 = md+1;
                vert = 1;
                continue;
            }

            int a = query(md-1, in), b = query(md+1, in);

            if(max(a, b) <= mx){
                printf("! %d %d 1\n", md, in);
                fflush(stdout);
                exit(0);
            }
            else if(a > b) r1 = md-1, ls = a, lsp = {md-1, in};
            else l1 = md+1, ls = b, lsp = {md+1, in};
            vert = 1;
        }
    }
}

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 if(k == 1) solve2d();
    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:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...