제출 #949230

#제출 시각아이디문제언어결과실행 시간메모리
949230koukirocksWorm Worries (BOI18_worm)C++17
26 / 100
58 ms1892 KiB
#include <bits/stdc++.h> #define speed ios_base::sync_with_stdio(0); cin.tie(0) #define all(x) (x).begin(),(x).end() #define F first #define S second using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll MAX=2e5+10,P=1e9+7; const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f; int n,m,k,q; const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int query(int x,int y,int z) { if (x>n or x<=0) return 0; if (y>m or y<=0) return 0; if (z>k or z<=0) return 0; cout<<"? "<<x<<" "<<y<<" "<<z<<"\n"<<flush; int ans; cin>>ans; if (ans==-1) exit(0); return ans; } pii dfs(int x,int y,int val,set<pii>& vis) { for (int k=0;k<4;k++) { int nx=x+dir[k][0]; int ny=y+dir[k][1]; if (vis.find(make_pair(nx,ny))==vis.end()) { int rlt=query(nx,ny,1); vis.insert({nx,ny}); if (rlt>val) { return dfs(nx,ny,rlt,vis); } } } return {x,y}; } struct pos { int x,y,z; pos (int _x,int _y,int _z):x(_x),y(_y),z(_z){}; bool operator<(pos a) const { if (this->x!=a.x) return x<a.x; if (this->y!=a.y) return y<a.y; return this->z<a.z; } }; const int dir2[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; pos dfs2(pos p,int val,set<pos>& vis) { for (int k=0;k<6;k++) { int nx=p.x+dir2[k][0]; int ny=p.y+dir2[k][1]; int nz=p.z+dir2[k][2]; if (vis.find(pos(nx,ny,nz))==vis.end()) { int rlt=query(nx,ny,nz); vis.insert(pos(nx,ny,nz)); if (rlt>val) { return dfs2(pos(nx,ny,nz),rlt,vis); } } } return p; } int main() { speed; cin>>n>>m>>k>>q; if (n==1000000) { mt19937 rnd(time(0)+3393848); uniform_int_distribution<int> pic(1,n); int maxx=0; int id=0; for (int i=0;i<n/5000;i++) { int now=pic(rnd); // cout<<now<<"\n"; int rlt=query(now,1,1); if (rlt>maxx) { maxx=rlt; id=now; } } int dir=0; if (query(id+1,1,1)>maxx) { dir=1; } if (query(id-1,1,1)>maxx) { dir=-1; } if (dir==0) { cout<<"! "<<id<<" 1 1\n"; return 0; } int now=id+dir; int val=query(now,1,1); int nxt=query(now+dir,1,1); while (nxt>val) { val=nxt; now+=dir; nxt=query(now+dir,1,1); } cout<<"! "<<now<<" 1 1"<<"\n"; } else if (n==200) { mt19937 rnd(time(0)+3393848); uniform_int_distribution<int> picx(1,n),picy(1,m); int maxx=0; pii id={0,0}; set<pii> vis; for (int i=0;i<n*m/400;i++) { int nx=picx(rnd); int ny=picy(rnd); // cout<<now<<"\n"; int rlt=query(nx,ny,1); if (rlt>maxx) { maxx=rlt; id={nx,ny}; } vis.insert({nx,ny}); } auto [x,y]=dfs(id.F,id.S,maxx,vis); cout<<"! "<<x<<" "<<y<<" 1"<<"\n"; } else if (n==100) { mt19937 rnd(time(0)+3393848); uniform_int_distribution<int> picx(1,n),picy(1,m),picz(1,k); int maxx=0; pos id(0,0,0); set<pos> vis; for (int i=0;i<n*m*k/5000;i++) { int nx=picx(rnd); int ny=picy(rnd); int nz=picz(rnd); // cout<<now<<"\n"; int rlt=query(nx,ny,nz); if (rlt>maxx) { maxx=rlt; id=pos(nx,ny,nz); } vis.insert(pos(nx,ny,nz)); } pos ans=dfs2(id,maxx,vis); cout<<"! "<<ans.x<<" "<<ans.y<<" "<<ans.z<<"\n"; } return 0; }
#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...