Submission #386263

#	Time	Username	Problem	Language	Result	Execution time	Memory
386263		maximath_1	Worm Worries (BOI18_worm)	C++11	100 / 100	1264 ms	500544 KiB

worm

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 200005;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1};
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

int n, m, k, q, queries_used = 0;
vector<vector<vector<int> > > v;

int cr_mx = 0, cr_x = 0, cr_y = 0, cr_z = 0;

int ask(int x, int y, int z){
	if(x < 1 || x > n || y < 1 || y > m || z < 1 || z > k)
		return -1;
	if(v[z - 1][y - 1][x - 1] != 0)
		return v[z - 1][y - 1][x - 1];

	cout << "? " << x << " " << y << " " << z << endl;
	int rs; cin >> rs;
	if(rs == -1) exit(0);
	v[z - 1][y - 1][x - 1] = rs;

	if(rs > cr_mx){
		cr_mx = rs;
		cr_x = x, cr_y = y, cr_z = z;
	}

	return rs;
}

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

bool ok(int x, int y, int z){
	vector<int> aa;
	aa.push_back(ask(x, y, z));
	for(int d = 0; d < 6; d ++)
		aa.push_back(ask(x + dx[d], y + dy[d], z + dz[d]));
	sort(aa.begin(), aa.end());
	if(aa.back() == ask(x, y, z))
		answer(x, y, z);
	return false;
}

mt19937 rng(time(NULL));

int main(){
	cin >> n >> m >> k;
	v.assign(k, vector<vector<int> >(m, vector<int>(n, 0)));
	cin >> q;

	if(m == k && k == 1){
		ld golden_ratio = (1.0 + sqrtl(5.0)) / 2.0;

		int lf = 1, rg = n, lastm1 = -1, lastm2 = -1;
		for(; rg - lf > 3;){
			int m1 = (int)ceil(rg - (ld)(rg - lf) / golden_ratio);
			int m2 = (int)floor(lf + (ld)(rg - lf) / golden_ratio);
			if(lastm1 != -1) m1 = lastm1, lastm1 = -1;
			if(lastm2 != -1) m2 = lastm2, lastm2 = -1;

			if(m1 == m2) break;

			if(ask(m1, 1, 1) < ask(m2, 1, 1)) lf = m1, lastm1 = m2;
			else rg = m2, lastm2 = m1;
		}

		for(int i = lf; i <= rg; i ++)
			ok(i, 1, 1);
	}else if(k == 1){
		int lfx = 1, rgx = n, lfy = 1, rgy = n;	
		for(; lfx < rgx || lfy < rgy;){
			if(rgx - lfx > rgy - lfy){
				int mdx = (lfx + rgx) / 2;
				for(int i = lfy; i <= rgy; i ++)
					ask(mdx, i, 1);

				if(mdx == cr_x) ok(cr_x, cr_y, cr_z);
				if(mdx >= cr_x) rgx = mdx;
				else lfx = mdx + 1;
			}else{
				int mdy = (lfy + rgy) / 2;
				for(int i = lfx; i <= rgx; i ++)
					ask(i, mdy, 1);

				if(mdy == cr_y) ok(cr_x, cr_y, cr_z);
				if(mdy >= cr_y) rgy = mdy;
				else lfy = mdy + 1;
			}
		}

		answer(lfx, lfy, 1);
	}

	int mx = -1, xx, yy, zz;

	for(int x, y, z; queries_used < q / 2; queries_used ++){
		x = rng() % n + 1;
		y = rng() % m + 1;
		z = rng() % k + 1;

		if(mx < ask(x, y, z)){
			mx = ask(x, y, z);
			xx = x, yy = y, zz = z;
		}
	}

	while(!ok(xx, yy, zz)){
		for(int d = 0; d < 6; d ++){
			int nx = xx + dx[d], ny = yy + dy[d], nz = zz + dz[d];
			if(ask(nx, ny, nz) > ask(xx, yy, zz)){
				xx = nx, yy = ny, zz = nz;
				break;
			}
		}
	}

	return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:135:11: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |  while(!ok(xx, yy, zz)){
      |         ~~^~~~~~~~~~~~
worm.cpp:135:11: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:135:11: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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