Submission #64114

#	Time	Username	Problem	Language	Result	Execution time	Memory
64114		babo	Worm Worries (BOI18_worm)	C++14	32 / 100	39 ms	740 KiB

worm

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,m,k,q;
L cnt;
const double distribution=2.61803398874;

struct S{
	L x,y,z;
};

bool operator<(S a,S b){
	if(a.x!=b.x) return a.x<b.x;
	if(a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
map<S,L>mp;

L ask(L x,L y,L z){
	if(x<1||x>n||y<1||y>m||z<1||z>k) return 0;
	if(mp[(S){x,y,z}]) return mp[(S){x,y,z}];
	cnt++;
	//printf("%lld\n",cnt);
	printf("? %lld %lld %lld\n",x,y,z);
	fflush(stdout);
	L ret;
	scanf("%lld",&ret);
	//return mp[(S){x,y,z}]=10000000-(x>5?x-5:5-x);
	if(ret==-1) exit(0);
	else return mp[(S){x,y,z}]=ret;
}

void answer(S ans){
	printf("! %lld %lld %lld\n",ans.x,ans.y,ans.z);
	exit(0);
}

L hf(double x){
	L ret=(L)x;
	if(x-ret>0.5) ret++;
	return ret;
}

void dim1(){
	L s=1,e=n,mi1=0,mi2=0,i,ma=0,mad;
	while(s<e-4)
	{
		if(!mi1&&!mi2)
		{
			mi1=s+hf((e-s)/distribution);
			mi2=e-hf((e-s)/distribution);
		}
		else if(!mi1)
		{
			mi1=s+hf((e-s)/distribution);
		}
		else if(!mi2)
		{
			mi2=e-hf((e-s)/distribution);
		}
		L lef=ask(mi1,1,1);
		L rig=ask(mi2,1,1);
		if(lef>rig)
		{
			e=mi2;
			mi2=mi1;
			mi1=0;
		}
		else
		{
			s=mi1;
			mi1=mi2;
			mi2=0;
		}
	}
	while(s<e)
	{
		L mi1=(s+e)/2;
		L mi2=mi1+1;
		L lef=ask(mi1,1,1);
		L rig=ask(mi2,1,1);
		if(lef>rig)
		{
			e=mi1;
		}
		else
		{
			s=mi2;
		}
	}
	answer((S){s,1,1});
}

void dim2(){
	L x1=1,y1=1,x2=n,y2=m,val=-1,lastx,lasty,vir=1;
	L i;
	while(x1<x2||y1<y2)
	{
		//printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
		if(vir)
		{
			L ymid=(y1+y2)/2;
			L ma=0,mad;
			for(i=x1;i<=x2;i++)
			{
				L temp=ask(i,ymid,1);
				if(temp>ma)
				{
					ma=temp;
					mad=i;
				}
			}
			L lef=ask(mad,ymid-1,1);
			L rig=ask(mad,ymid+1,1);
			if(ma>=lef&&ma>=rig) answer((S){mad,ymid,1});
			if(val>=ma)
			{
				if(ymid>lasty)
				{
					y2=ymid-1;
					val=lef;
				}
				else
				{
					y1=ymid+1;
					val=rig;
				}
			}
			else
			{
				if(lef>rig)
				{
					y2=ymid-1;
					val=lef;
				}
				else
				{
					y1=ymid+1;
					val=rig;
				}
			}
			lastx=mad;
		}
		else
		{
			L xmid=(x1+x2)/2;
			L ma=0,mad;
			for(i=y1;i<=y2;i++)
			{
				L temp=ask(xmid,i,1);
				if(temp>ma)
				{
					ma=temp;
					mad=i;
				}
			}
			L up=ask(xmid-1,mad,1);
			L dwo=ask(xmid+1,mad,1);
			if(ma>=up&&ma>=dwo) answer((S){xmid,mad,1});
			if(val>=ma)
			{
				if(xmid>lastx)
				{
					x2=xmid-1;
					val=up;
				}
				else
				{
					x1=xmid+1;
					val=dwo;
				}
			}
			else
			{
				if(up>dwo)
				{
					x2=xmid-1;
					val=up;
				}
				else
				{
					x1=xmid+1;
					val=dwo;
				}
			}
			lasty=mad;
		}
		vir^=1;
	}
	answer((S){x1,y1,1});
}

void dim3(){
	
}

int main()
{
	srand((int)time(NULL));
	scanf("%lld %lld %lld %lld",&n,&m,&k,&q);	
	if(m==1&&k==1)
	{
		dim1();
	}
	else if(k==1)
	{
		dim2();
	}
	else
	{
		dim3();
	}
}

Compilation message (stderr)

worm.cpp: In function 'void dim1()':
worm.cpp:47:24: warning: unused variable 'i' [-Wunused-variable]
  L s=1,e=n,mi1=0,mi2=0,i,ma=0,mad;
                        ^
worm.cpp:47:26: warning: unused variable 'ma' [-Wunused-variable]
  L s=1,e=n,mi1=0,mi2=0,i,ma=0,mad;
                          ^~
worm.cpp:47:31: warning: unused variable 'mad' [-Wunused-variable]
  L s=1,e=n,mi1=0,mi2=0,i,ma=0,mad;
                               ^~~
worm.cpp: In function 'long long int ask(long long int, long long int, long long int)':
worm.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&ret);
  ~~~~~^~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:202:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld",&n,&m,&k,&q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'void dim2()':
worm.cpp:117:31: warning: 'mad' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(ma>=lef&&ma>=rig) answer((S){mad,ymid,1});
                         ~~~~~~^~~~~~~~~~~~~~~~~
worm.cpp:120:5: warning: 'lasty' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(ymid>lasty)
     ^~

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