Submission #861493

#	Time	Username	Problem	Language	Result	Execution time	Memory
861493		Trisanu_Das	Worm Worries (BOI18_worm)	C++17	59 / 100	589 ms	6828 KiB

worm

//Randomization OP!!
#include <bits/stdc++.h>
using namespace std;
 
int n, m, k, q;
int dx[] = {1, 0, 0, -1, 0, 0}; 
int dy[] = {0, 1, 0, 0, -1, 0}; 
int dz[] = {0, 0, 1, 0, 0, -1};
map<tuple<int,int,int>,int> save;
mt19937 rng(time(0));
 
int ask(int a,int b,int c){
	if(save.find({a, b, c}) != save.end()) return save[{a, b, c}];
	cout << "? " << a << ' ' << b << ' ' << c << endl;
	int x; cin >> x;
	return save[{a, b, c}] = x;
}
 
void submit(int a,int b,int c){
	cout << "! " << a << ' ' << b << ' ' << c << endl; 
	exit(0);
}
 
int bad(int a, int b, int c){
	return a <= 0 || b <= 0 || c <= 0 || a > n || b > m || c > k;
}
 
int main(){
	cin >> n >> m >> k >> q;
	int Q = q;
	tuple<int,int,int,int> ans = {0,0,0,0};
	for(int i = 0; i < (Q >> 1); i++){
		int x = rng() % n + 1, y = rng() % m + 1, z = rng() % k + 1;
		ans = max(ans, {ask(x , y , z), x, y, z});
	}
	auto[cur, x, y, z] = ans;
	while(q){
		bool done=true;
		for(int i = 0; i < 6; i++){
			int nx = x + dx[i], ny = y + dy[i], nz = z+dz[i];
			if(bad(nx, ny, nz)) continue;
			int res = ask(nx, ny, nz);
			if(res > cur){
				cur = res; x = nx; y = ny; z=nz;
				done = false;
				break;
			}
		}
		if(done) break;
	}
	submit(x, y, z);
}

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