Submission #398242

#	Time	Username	Problem	Language	Result	Execution time	Memory
398242		AmineWeslati	Worm Worries (BOI18_worm)	C++14	37 / 100	1281 ms	499392 KiB

worm

#include "bits/stdc++.h"
using namespace std; 

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
typedef string str;
#define FOR(i,a,b) for(int i=a; i<b; i++)

void IO(){
#ifdef LOCAL
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
}
//------------------------------------------------------//

void ckmin(int &x, int y){x=min(x,y);}
bool ckmax(int &x, int y){
	if(y>x){
		x=y; 
		return 1;
	}
	return 0;
}

int random(int r){
	return rand()%r+1;
}

const int MX=1e6+10;
const int dx[6]={1,-1,0,0,0,0},dy[6]={0,0,1,-1,0,0},dz[6]={0,0,0,0,1,-1};

int N,M,K,Q;
vector<vector<vector<int>>>memo;

int g[1000][1000];

int lx,ly,lz,rx,ry,rz;
int get(int x, int y, int z){
	//if(x<lx || y<ly || z<lz || x>rx || y>ry || z>rz) return 0;
	if(x<1 || y<1 || z<1 || x>N || y>M || z>K) return 0;
	//return g[x][y];
	if(memo[x][y][z]!=-1) return memo[x][y][z];
	cout << "? " << x << ' ' << y << ' ' << z << endl;
	int val; cin>>val;
	return memo[x][y][z]=val;
}

void answer(int x, int y, int z){
	/*FOR(m,0,6){
		int nx=x+dx[m],ny=y+dy[m],nz=z+dz[m];
		assert(get(nx,ny,nz)<=get(x,y,z));
	}*/
	cout << "! " << x << ' ' << y << ' ' << z << endl;
	cout.flush();
	exit(0);
}

bool check(int x, int y, int lx, int rx, int ly, int ry){
	return x>=lx && x<=rx && y>=ly && y<=ry;
}


int main(){
	IO();

	cin>>N>>M>>K>>Q;
	lx=ly=lz=1; 
	rx=N; ry=M; rz=K;

	memo.resize(N+1);
	FOR(i,1,N+1){
		memo[i].resize(M+1);
		FOR(j,1,M+1) memo[i][j].assign(K+1,-1);
	}



	if(K!=1){ //3D
		int rep=Q/2,mx=0,x,y,z;
		while(rep--){
			int xx=random(N),yy=random(M),zz=random(K);
			if(ckmax(mx,get(xx,yy,zz))){
				x=xx; y=yy; z=zz; 
			}
		}

		while(1){
			int f=0;
			FOR(m,0,6){
				int nx=x+dx[m],ny=y+dy[m],nz=z+dz[m];
				if(get(nx,ny,nz)>get(x,y,z)){
					f=1;
					x=nx; y=ny; z=nz; 
					break;
				}
			}
			if(!f) break;
		}
		answer(x,y,z);
	}
	else{ //2D

		int px,py,pmx=0;
		while(lx<=rx && ly<=ry){
			//cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
			if(rx-lx>=ry-ly){
				int x=(lx+rx)/2,y=-1,mx=-1;
				FOR(Y,ly,ry+1){
					//if(!(max(get(x,Y-1,1),get(x,Y+1,1))<=get(x,Y,1))) continue;

					if(ckmax(mx,get(x,Y,1))) y=Y;
				}
				assert(y!=-1);

				if(mx<pmx){
					if(check(px,py,lx,x-1,ly,ry)) rx=x-1;
					else lx=x+1;
				}
				else{
					int v=get(x-1,y,1),vv=get(x+1,y,1);
					if(get(x,y,1)>=max(v,vv)) answer(x,y,1);
					if(v>get(x,y,1) && x-1>=lx) rx=x-1;
					else lx=x+1;

					pmx=mx; px=x; py=y;
				}

				
			}
			else{
				int y=(ly+ry)/2,x=-1,mx=-1;
				FOR(X,lx,rx+1){
					//if(!(max(get(X-1,y,1),get(X+1,y,1))<=get(X,y,1))) continue;
					if(ckmax(mx,get(X,y,1))) x=X;
				}
				assert(x!=-1);

				if(mx<pmx){
					if(check(px,py,lx,ry,ly,y-1)) ry=y-1;
					else ly=y+1;
				}
				else{
					int v=get(x,y-1,1),vv=get(x,y+1,1);
					if(get(x,y,1)>=max(v,vv)) answer(x,y,1);
					if(v>get(x,y,1) && y-1>=ly) ry=y-1;
					else ly=y+1;
				}
				pmx=mx; px=x; py=y;
				
			}
		}
		assert(0);
	}
	
	
	
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:62:37: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  return x>=lx && x<=rx && y>=ly && y<=ry;
      |                                    ~^~~~
worm.cpp:106:10: note: 'py' was declared here
  106 |   int px,py,pmx=0;
      |          ^~
worm.cpp:62:19: warning: 'px' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  return x>=lx && x<=rx && y>=ly && y<=ry;
      |                  ~^~~~
worm.cpp:106:7: note: 'px' was declared here
  106 |   int px,py,pmx=0;
      |       ^~
worm.cpp:102:9: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |   answer(x,y,z);
      |   ~~~~~~^~~~~~~
worm.cpp:102:9: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:102:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23