oj.uz

Submission #386263

# Submission time Handle Problem Language Result Execution time Memory
386263 2021-04-06T08:42:59 Z maximath_1 Worm Worries (BOI18_worm) C++11
100 / 100
 1264 ms 500544 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12012 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct
3 Correct 8 ms 12012 KB Output is correct
4 Correct 8 ms 12012 KB Output is correct
5 Correct 8 ms 12012 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12012 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct
3 Correct 8 ms 12012 KB Output is correct
4 Correct 8 ms 12012 KB Output is correct
5 Correct 8 ms 12084 KB Output is correct
6 Correct 9 ms 12012 KB Output is correct
7 Correct 9 ms 12012 KB Output is correct
8 Correct 11 ms 12012 KB Output is correct
9 Correct 10 ms 12012 KB Output is correct
10 Correct 9 ms 12012 KB Output is correct
11 Correct 9 ms 12012 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 6 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 9 ms 620 KB Output is correct
5 Correct 9 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 4 ms 620 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8172 KB Output is correct
2 Correct 30 ms 8172 KB Output is correct
3 Correct 16 ms 8300 KB Output is correct
4 Correct 22 ms 8172 KB Output is correct
5 Correct 33 ms 8172 KB Output is correct
6 Correct 23 ms 8300 KB Output is correct
7 Correct 43 ms 8300 KB Output is correct
8 Correct 36 ms 8172 KB Output is correct
9 Correct 39 ms 8300 KB Output is correct
10 Correct 25 ms 8300 KB Output is correct
11 Correct 50 ms 8300 KB Output is correct
12 Correct 35 ms 8172 KB Output is correct
13 Correct 34 ms 8288 KB Output is correct
14 Correct 39 ms 8172 KB Output is correct
15 Correct 35 ms 8300 KB Output is correct
16 Correct 23 ms 8172 KB Output is correct
17 Correct 41 ms 8172 KB Output is correct
18 Correct 23 ms 8288 KB Output is correct
19 Correct 28 ms 8172 KB Output is correct
20 Correct 24 ms 8172 KB Output is correct
21 Correct 30 ms 8172 KB Output is correct
22 Correct 43 ms 8172 KB Output is correct
23 Correct 35 ms 8172 KB Output is correct
24 Correct 36 ms 8288 KB Output is correct
25 Correct 35 ms 8172 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4844 KB Output is correct
2 Correct 446 ms 4732 KB Output is correct
3 Correct 436 ms 4844 KB Output is correct
4 Correct 439 ms 4844 KB Output is correct
5 Correct 385 ms 4732 KB Output is correct
6 Correct 452 ms 4844 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 500416 KB Output is correct
2 Correct 995 ms 500416 KB Output is correct
3 Correct 983 ms 500460 KB Output is correct
4 Correct 1020 ms 500416 KB Output is correct
5 Correct 922 ms 500416 KB Output is correct
6 Correct 1106 ms 500416 KB Output is correct
7 Correct 983 ms 500460 KB Output is correct
8 Correct 985 ms 500332 KB Output is correct
9 Correct 1264 ms 500544 KB Output is correct
10 Correct 1242 ms 500460 KB Output is correct
11 Correct 995 ms 500416 KB Output is correct