제출 #986189

#제출 시각아이디문제언어결과실행 시간메모리
986189ByeWorldWorm Worries (BOI18_worm)C++14
0 / 100
3029 ms2028 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<4; 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){ exit(0); 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 mx = -1, a=-1, b=num(m), c=1; bool type = 0; for(int i=1; i<=n; i++){ if(mx < que(i, b, c)){ mx = que(i, b, c); a = i; type = 1; } } a=1; b=1; c=1; while(all+4<q){ if(aman(a, b, c)) break; // cout << a << ' ' << b << ' ' << c << " abc\n"; // cout << type << " ty\n"; if(type){ // cek column bool ri = 0; if(que(a, b+1, c) == 0){ if(que(a, b, c) > que(a, b-1, c)) ri = 1; } else if(que(a, b, c) < que(a, b+1, c)) ri = 1; int mx = -1; if(ri){ for(int i=b; i<=m; i++){ if(mx < que(a, i, c)){ mx = que(a, i, c); b = i; } } } else { for(int i=1; i<=b; i++){ if(mx < que(a, i, c)){ mx = que(a, i, c); b = i; } } } type = 0; } else {// cek row bool ri = 0; if(que(a+1, b, c) == 0){ if(que(a, b, c) > que(a-1, b, c)) ri = 1; } else if(que(a, b, c) < que(a+1, b, c)) ri = 1; int mx = -1; if(ri){ for(int i=a; i<=m; i++){ if(mx < que(i, b, c)){ mx = que(i, b, c); a = i; } } } else { for(int i=1; i<=a; i++){ if(mx < que(i, b, c)){ mx = que(i, b, c); a = i; } } } type = 1; } } cout << "! " <<a<<' '<<b<<' '<<c<<endl; exit(0); } 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...