Submission #386243

#	Time	Username	Problem	Language	Result	Execution time	Memory
386243		maximath_1	Worm Worries (BOI18_worm)	C++11	59 / 100	1384 ms	500460 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 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;
	v[z - 1][y - 1][x - 1] = rs;
	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)) return true;
	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){
		int lf = 1, rg = n;
		for(int md; lf < rg;){
			md = (lf + rg) / 2;
			if(ask(md, 1, 1) > ask(md + 1, 1, 1))
				rg = md;
			else
				lf = md + 1;
		}
		answer(lf, 1, 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;
			}
		}
	}

	answer(xx, yy, zz);

	return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:104:8: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |  answer(xx, yy, zz);
      |  ~~~~~~^~~~~~~~~~~~
worm.cpp:104:8: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:104:8: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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