Submission #266480

#	Time	Username	Problem	Language	Result	Execution time	Memory
266480		TadijaSebez	Worm Worries (BOI18_worm)	C++11	100 / 100	981 ms	5968 KiB

worm

#include <bits/stdc++.h>
using namespace std;
#define ldb double
map<array<int,3>,int> was;
int n,m,k,q;
int Ask(int i,int j,int k){
	if(was.count({i,j,k}))return was[{i,j,k}];
	if(i<1||j<1||k<1||i>n||j>m||k>::k)return 0;
	printf("? %i %i %i\n",i,j,k);
	fflush(stdout);
	int b;scanf("%i",&b);
	was[{i,j,k}]=b;
	return b;
}
void Ans(int i,int j,int k){
	printf("! %i %i %i\n",i,j,k);
	fflush(stdout);
	exit(0);
}
bool Check(int i,int j,int k){
	int now=Ask(i,j,k);
	for(int a=-1;a<=1;a+=2)
		if(now<max({Ask(i+a,j,k),Ask(i,j+a,k),Ask(i,j,k+a)}))
			return 0;
	Ans(i,j,k);
	return 1;
}
mt19937 rng(time(0));
const ldb f1=0.618,f2=0.382;
int main(){
	scanf("%i %i %i %i",&n,&m,&k,&q);
	if(m==1&&k==1){
		int top=n,bot=1,mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top),las=0;
		while(top-bot>=5){
			if(mid1>=mid2){
				mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top);
				if(mid1>=mid2)break;
			}
			if(Ask(mid1,1,1)<Ask(mid2,1,1)){
				bot=mid1+1;
				tie(mid1,mid2)=make_pair(mid2,round(f2*bot+f1*top));
			}else{
				top=mid2-1;
				tie(mid1,mid2)=make_pair(round(f1*bot+f2*top),mid1);
			}
		}
		for(int i=bot;i<=top;i++)Check(i,1,1);
	}else if(k==1){
		int X1=1,X2=n,Y1=1,Y2=m,Xm,Ym,last=0;
		pair<int,int> pre;
		while(X1<=X2&&Y1<=Y2){
			Xm=X1+X2>>1;
			int mx=0,pos=0;
			for(int i=Y1;i<=Y2;i++){
				int now=Ask(Xm,i,1);
				if(now>mx)mx=now,pos=i;
			}
			if(mx<last){
				if(Xm-1>=pre.first)X2=Xm-1;
				else X1=Xm+1;
			}else{
				if(Ask(Xm-1,pos,1)>mx){
					X2=Xm-1;
					pre={Xm-1,pos};
				}else if(Ask(Xm+1,pos,1)>mx){
					X1=Xm+1;
					pre={Xm+1,pos};
				}else Ans(Xm,pos,1);
				last=mx;
			}
			Ym=Y1+Y2>>1;
			mx=0,pos=0;
			for(int i=X1;i<=X2;i++){
				int now=Ask(i,Ym,1);
				if(now>mx)mx=now,pos=i;
			}
			if(mx<last){
				if(Ym-1>=pre.second)Y2=Ym-1;
				else Y1=Ym+1;
			}else{
				if(Ask(pos,Ym-1,1)>mx){
					Y2=Ym-1;
					pre={pos,Ym-1};
				}else if(Ask(pos,Ym+1,1)>mx){
					Y1=Ym+1;
					pre={pos,Ym+1};
				}else Ans(pos,Ym,1);
				last=mx;
			}
		}
	}else{
		int X,Y,Z,mx=0;
		for(int i=1;i<=q/2;i++){
			int x=rng()%n+1;
			int y=rng()%m+1;
			int z=rng()%k+1;
			if(Ask(x,y,z)>mx){
				mx=Ask(x,y,z);
				X=x;
				Y=y;
				Z=z;
			}
		}
		while(!Check(X,Y,Z)){
			if(Ask(X+1,Y,Z)>Ask(X,Y,Z))X++;
			else if(Ask(X-1,Y,Z)>Ask(X,Y,Z))X--;
			else if(Ask(X,Y+1,Z)>Ask(X,Y,Z))Y++;
			else if(Ask(X,Y-1,Z)>Ask(X,Y,Z))Y--;
			else if(Ask(X,Y,Z+1)>Ask(X,Y,Z))Z++;
			else if(Ask(X,Y,Z-1)>Ask(X,Y,Z))Z--;
		}
	}
	return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:33:71: warning: unused variable 'las' [-Wunused-variable]
   33 |   int top=n,bot=1,mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top),las=0;
      |                                                                       ^~~
worm.cpp:52:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |    Xm=X1+X2>>1;
      |       ~~^~~
worm.cpp:71:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |    Ym=Y1+Y2>>1;
      |       ~~^~~
worm.cpp: In function 'int Ask(int, int, int)':
worm.cpp:11:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  int b;scanf("%i",&b);
      |        ~~~~~^~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%i %i %i %i",&n,&m,&k,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:110:28: warning: 'Z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |    else if(Ask(X,Y,Z-1)>Ask(X,Y,Z))Z--;
      |                         ~~~^~~~~~~
worm.cpp:110:28: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:110:28: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]

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