Submission #1361716

#TimeUsernameProblemLanguageResultExecution timeMemory
1361716NonozeWorm Worries (BOI18_worm)C++20
81 / 100
570 ms999852 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)x.size()
#define int long long

void solve();
mt19937 rng(132309);

signed main() {
	ios::sync_with_stdio(0);
	solve();
	return 0;
}


int n, m, k, q;
vector<vector<vector<int>>> queriess;

int cnt=0;

int ask(int x, int y, int z) {
	if (x<=0 || y<=0 || z<=0 || x>n || y>m || z>k) return 0;
	if (queriess[x][y][z]!=-1) return queriess[x][y][z];
	cnt++;
	// return queriess[x][y][z]=rand()%n;
	cout << "? " << x << ' ' << y << ' ' << z << endl;
	int res; cin >> res;
	return queriess[x][y][z]=res;
}

void finish(int x, int y, int z) {
	cout << "! " << x << ' ' << y << ' ' << z << endl;
	exit(0);
}

long double mul1=(sqrt(5)-1)/2, mul2=1-mul1;


void solve() {
	cin >> n >> m >> k >> q;
	queriess.resize(n+1, vector<vector<int>>(m+1, vector<int>(k+1, -1)));
	if (m==1 && k==1) {
		int l=1, r=n;
		int mid1=l + (long double)(r-l)*mul2, mid2= l + (long double)(r-l)*mul1;
		while (r-l>5) {
			assert(mid1<mid2);
			int res1=ask(mid1, 1, 1), res2=ask(mid2, 1, 1);
			if (res2>=res1) {
				l=mid1;
				mid1=mid2, mid2=l + ceil((long double)(r-l)*mul1);
				if (mid1==mid2) mid2++;
			} else {
				r=mid2;
				mid2=mid1, mid1=l + (long double)(r-l)*mul2;
				if (mid1==mid2) mid1--;
			}
		}
		int ans=-1;
		for (int i=l; i<=r; i++) {
			if (ask(i, 1, 1)>=ask(i-1, 1, 1) && ask(i, 1, 1)>=ask(i+1, 1, 1)) {
				ans=i;
				break;
			}
		}
		finish(ans, 1, 1);
	}
	vector<pair<int, vector<int>>> points;
	for (int i=0; i<q/2; i++) {
		int x=uniform_int_distribution<int>(1, n)(rng), y=uniform_int_distribution<int>(1, m)(rng), z=uniform_int_distribution<int>(1, k)(rng);
		points.pb({ask(x, y, z), {i, x, y, z}});
	}
	sort(rall(points));
	int x=points[0].se[1], y=points[0].se[2], z=points[0].se[3];
	vector<vector<int>> modifs={
		{1, 0, 0},
		{-1, 0, 0},
		{0, 1, 0},
		{0, -1, 0},
		{0, 0, 1},
		{0, 0, -1}
	};
	while (1) {
		vector<int> best; int val=0;
		for (auto &vec: modifs) {
			int res=ask(x+vec[0], y+vec[1], z+vec[2]);
			if (res>val) val=res, best=vec;
		}
		if (val<=ask(x, y, z)) break;
		x+=best[0], y+=best[1], z+=best[2];
	}
	finish(x, y, z);
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...