Submission #1188070

#TimeUsernameProblemLanguageResultExecution timeMemory
1188070kl0989eWorm Worries (BOI18_worm)C++20
0 / 100
216 ms5012 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 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;
	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);
}

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);
	
	/*int l=1,r=n;
	while (l<r) {
		int m=l+(r-l)/2;
		if (query(m)>=query(m+1)) {
			r=m;
		}
		else {
			l=m+1;
		}
	}
	guess(l);*/
	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+ax[i];
				mx=query(nx,ny,nz);
			}
		}
		if (mx<=query(x,y,z)) {
			guess(x,y,z);
		}
		x=nx;
		y=ny;
		z=nz;
	}
}

Compilation message (stderr)

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