제출 #1188161

#제출 시각아이디문제언어결과실행 시간메모리
1188161kl0989eWorm Worries (BOI18_worm)C++20
100 / 100
256 ms5784 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

map<array<int,3>,int> mem;
int n, m, k, q;

int mxx=-1,mxy=-1;

int query(int x=1, int y=1, int z=1) {
	if (mem.count({x,y,z})) {
		return mem[{x,y,z}]; 
	}
	if (x<1 || n<x || y<1 || m<y || z<1 || k<z) {
		return 0;
	}
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	int ans = -1;
	(void)scanf("%d", &ans);
	if (ans == -1) exit(0);
	mem[{x,y,z}]=ans;
	if (k==1 && mem[{mxx,mxy,1}]<ans) {
		mxx=x;
		mxy=y;
	}
	return ans;
}

__attribute__((noreturn))
void guess(int x=1, int y=1, int z=1) {
	printf("! %d %d %d\n", x, y, z);
	exit(0);
}

double phi=(1+sqrt(5))/2;

int mean(int l, int r) {
	return l+(r-l+1)/phi;
}

int find(int l, int r, int x) {
	if (l==r) {
		return x;
	}
	int y=mean(l,r);
	if(2*x>l+r) {
		y=l+r-y;
	}
	if (x==y) {
		y++;
	}
	if (x>y) {
		swap(x,y);
	}
	if (query(x)<=query(y)) {
		return find(x+1,r,y);
	}
	else {
		return find(l,y-1,x);
	}
}

vi ax={1,-1,0,0,0,0};
vi ay={0,0,1,-1,0,0};
vi az={0,0,0,0,1,-1};

int main() {
	(void)scanf("%d %d %d %d", &n, &m, &k, &q);
	if (m==1 && k==1) {
		guess(find(1,n,mean(1,n)));
	}
	if (k==1) {
		int lx=1,rx=n;
		int ly=1,ry=m;
		for (int i=0; lx<=rx && ly<=ry; i++) {
			if (i%2) {
				int mix=lx+(rx-lx)/2;
				int tmx=-1;
				for (int j=ly; j<=ry; j++) {
					if (query(mix,j)>query(mix,tmx)) {
						tmx=j;
					}
				}
				bool ok=1;
				for (int j=0; j<4; j++) {
					if (query(mix+ax[j],tmx+ay[j])>query(mix,tmx)) {
						ok=0;
						break;
					}
				}
				if (ok) {
					mxx=mix;
					mxy=tmx;
					break;
				}
				if (mxx>mix) {
					lx=mix+1;
				}
				else {
					rx=mix-1;
				}
			}
			else {
				int mix=ly+(ry-ly)/2;
				int tmx=-1;
				for (int j=lx; j<=rx; j++) {
					if (query(j,mix)>query(tmx,mix)) {
						tmx=j;
					}
				}
				bool ok=1;
				for (int j=0; j<4; j++) {
					if (query(tmx+ax[j],mix+ay[j])>query(tmx,mix)) {
						ok=0;
						break;
					}
				}
				if (ok) {
					mxx=tmx;
					mxy=mix;
					break;
				}
				if (mxy>mix) {
					ly=mix+1;
				}
				else {
					ry=mix-1;
				}
			}
		}
		guess(mxx,mxy);
	}
	mt19937_64 rnd(time(0));
	int mx=-1,x,y,z;
	for (int i=0; i<q/2; i++) {
		int tx=rnd()%n+1;
		int ty=rnd()%m+1;
		int tz=rnd()%k+1;
		if (query(tx,ty,tz)>mx) {
			mx=query(tx,ty,tz);
			x=tx;
			y=ty;
			z=tz;
		}
	}
	while (1) {
		mx=-1;
		int nx,ny,nz;
		for (int i=0; i<6; i++) {
			if (query(x+ax[i],y+ay[i],z+az[i])>mx) {
				nx=x+ax[i];
				ny=y+ay[i];
				nz=z+az[i];
				mx=query(nx,ny,nz);
			}
		}
		if (mx<=query(x,y,z)) {
			guess(x,y,z);
		}
		x=nx;
		y=ny;
		z=nz;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:29:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         (void)scanf("%d", &ans);
      |               ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:78:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         (void)scanf("%d %d %d %d", &n, &m, &k, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...