Submission #1098744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098744		vjudge1	Worm Worries (BOI18_worm)	C++17	0 / 100	1231 ms	18208 KiB

worm

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int N = 2e5 + 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int X = 100;

map<ar<int, 3>, int> mp;

int qry(int a, int b,int c){
	if(mp.count({a, b, c}))return mp[{a, b, c}];
	cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
	int x;
	cin>>x;
	return mp[{a, b, c}] = x;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n, m, k, q;
	cin>>n>>m>>k>>q;
	map<ar<int, 3>, int> mp;
	for(int i = 0;i < q / 2;i++){
		int x = rng() % n + 1;
		int y = rng() % m + 1;
		int z = rng() % k + 1;
		while(mp.count({x, y, z})){
			x = rng() % n + 1;
			y = rng() % m + 1;
			z = rng() % k + 1;
		}
		mp[{x, y, z}] = qry(x, y, z);
	}
	auto [x, y, z] = mp.rbegin()->first;
	for(int i = q / 2;i < q;i++){
		bool f = 0;
		for(auto dx : {-1, 1}){
			if(f)continue;
			if(x + dx <= 0 || x + dx > n)continue;
			if(qry(x + dx, y, z) > qry(x, y, z)){
				x += dx;
				f = 1;
			}
		}
		for(auto dy : {-1, 1}){
			if(f)continue;
			if(y + dy <= 0 || y + dy > m)continue;
			if(qry(x, y + dy, z) > qry(x, y, z)){
				y += dy;
				f = 1;
			}
		}
		for(auto dz : {-1, 1}){
			if(f)continue;
			if(z + dz <= 0 || z + dz > k)continue;
			if(qry(x, y, z + dz) > qry(x, y, z)){
				z += dz;
				f = 1;
			}
		}
			
		if(!f){
			cout<<"! "<<x<<" "<<y<<" "<<z<<endl;
			return 0;
		}
	}
}	

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