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...