제출 #986385

#제출 시각아이디문제언어결과실행 시간메모리
986385ByeWorldWorm Worries (BOI18_worm)C++14
100 / 100
590 ms8160 KiB
#include <bits/stdc++.h> #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii,int> ipii; vector <int> vx = {1, -1, 0, 0, 0, 0}; vector <int> vy = {0, 0, 1, -1, 0, 0}; vector <int> vz = {0, 0, 0, 0, 1, -1}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int all, n, m, k, q; int ansx=-1, ansy, ansz; map <ipii, int> ma; int num(int r){ int x = rng(); x = abs(x); x %= r; x++; return x; } int que(int a, int b, int c){ if(a<=0 || a>n || b<=0 || b>m || c<=0 || c>k) return 0; if(ma.count(ipii(pii(a, b), c)) != 0) return ma[ipii(pii(a, b), c)]; if(all == q) assert(false); cout << "? " << a << ' ' << b << ' ' << c << endl; all++; int x; cin >> x; ma[ipii(pii(a, b), c)] = x; return x; } bool aman(int a, int b, int c){ if(a<=0 || a>n || b<=0 || b>m || c<=0 || c>k) return 0; for(int i=0; i<6; i++){ if(que(a, b, c) < que(a+vx[i], b+vy[i], c+vz[i])) return 0; } return 1; } signed main(){ cin >> n >> m >> k >> q; if(m==1 && k==1){ int len = n; int l=1, r=n, mid1=-1, mid2=-1; while(r-l+1 >= 4){ len = r-l+1; if(mid1==-1) mid1 = l+0.382*len; if(mid2==-1) mid2 = l+0.618*len; if(mid1 >= mid2){ mid1 = l+0.382*len; mid2 = l+0.618*len; if(mid1 >= mid2) break; } if(que(mid1, 1, 1) <= que(mid2, 1, 1)){ l = mid1; mid1 = mid2; mid2 = -1; } else { r = mid2; mid2 = mid1; mid1 = -1; } } int ans = l; for(int i=l; i<=r; i++){ if(que(i, 1, 1) >= max(que(i+1, 1, 1), que(i-1, 1, 1))){ ans = i; break; } } // assert(ans != -1); cout << "! " << ans << " 1 1" << endl; exit(0); } if(k==1){ int lx=1, rx=n, ly=1, ry=m; bool type = 1; pii nw = {-1, -1}; int val = -1; while(lx<rx || ly<ry){ if(lx==rx) type = 1; if(ly==ry) type = 0; if(type){ // vert int mid = (lx+rx)/2, mx=-1, idx=-1; for(int i=ly; i<=ry; i++){ if(mx < que(mid, i, 1)){ mx = que(mid, i, 1); idx = i; } } if(aman(mid, idx, 1)){ lx = mid; ly = idx; break; } if(val > que(mid, idx, 1)){ // nw lebih optimal if(nw.fi < mid) rx = mid-1; else lx = mid+1; } else { nw = {mid, idx}; val = que(mid, idx, 1); int le = que(mid-1, idx, 1), ri = que(mid+1, idx, 1); if(le < ri){ // ke kanan lx = mid+1; } else rx = mid-1; } } else { // hor int mid = (ly+ry)/2, mx=-1, idx=-1; for(int i=lx; i<=rx; i++){ if(mx < que(i, mid, 1)){ mx = que(i, mid, 1); idx = i; } } if(aman(idx, mid, 1)){ lx = idx; ly = mid; break; } if(val > que(idx, mid, 1)){ if(nw.se < mid) ry = mid-1; else ly = mid+1; } else { nw = {idx, mid}; val = que(idx, mid, 1); if(que(idx, mid-1, 1) < que(idx, mid+1, 1)){ // ke kanan ly = mid+1; } else ry = mid-1; } } type = !type; } cout << "! " << lx << ' '<< ly << " 1" << endl; exit(0); } int mx = -1, a=-1, b=-1, c=-1; for(int i=0; i<q/2; i++){ int x=num(n), y=num(m), z=num(k); if(mx < que(x,y,z)){ mx=que(x,y,z); a=x; b=y; c=z; } } while(all+6<q){ if(aman(a, b, c)) break; int mx = -1, x=-1,y=-1,z=-1; for(int i=0; i<6; i++){ if(mx < que(a+vx[i], b+vy[i], c+vz[i])){ mx=que(a+vx[i], b+vy[i], c+vz[i]); x=a+vx[i]; y=b+vy[i]; z=c+vz[i]; } } a=x; b=y; c=z; } cout << "! " <<a<<' '<<b<<' '<<c<<endl; }
#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...