Submission #398231

#	Time	Username	Problem	Language	Result	Execution time	Memory
398231		AmineWeslati	Worm Worries (BOI18_worm)	C++14	47 / 100	1226 ms	499456 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 get(int x, int y, int z){
	if(min(x,min(y,z))<1 || x>N || y>M || z>K) return 0;
	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){
	cout << "! " << x << ' ' << y << ' ' << z << endl;
	cout.flush();
	exit(0);
}


int main(){
	IO();

	cin>>N>>M>>K>>Q;
	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 lx=1,ly=1,rx=N,ry=M;
		while(lx<=rx && ly<=ry){
			if(rx-lx>=ry-ly){
				int x=(lx+rx)/2,y,mx=0;
				FOR(Y,ly,ry+1){
					if(ckmax(mx,get(x,Y,1))) y=Y;
				}

				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)) rx=x-1;
				else lx=x+1;
			}
			else{
				int y=(ly+ry)/2,x,mx=0;
				FOR(X,lx,rx+1){
					if(ckmax(mx,get(X,y,1))) x=X;
				}
				
				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)) ry=y-1;
				else ly=y+1;
			}
		}
		assert(0);
	}
	
	
	
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:108:37: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     if(get(x,y,1)>=max(v,vv)) answer(x,y,1);
      |                               ~~~~~~^~~~~~~
worm.cpp:97:37: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     if(get(x,y,1)>=max(v,vv)) answer(x,y,1);
      |                               ~~~~~~^~~~~~~
worm.cpp:85:9: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |   answer(x,y,z);
      |   ~~~~~~^~~~~~~
worm.cpp:85:9: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:85:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

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