Submission #1098758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098758		vjudge1	Worm Worries (BOI18_worm)	C++17	68 / 100	645 ms	7768 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;

int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};

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

int n, m, k;

int all = 0;

int qry(int a, int b,int c){
	if(a <= 0 || a > n || b <= 0 || b > m || c <= 0 || c > k)return 0;
	if(mp.count({a, b, c}))return mp[{a, b, c}];
	cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
	int x;
	cin>>x;
	++all;
	return mp[{a, b, c}] = x;
}

bool check(int x,int y,int z){
	if(x <= 0 || x > n || y <= 0 || y > m || z <= 0 || z > k)return 0;
	for(int i= 0;i < 6;i++){
		if(qry(x, y, z) < qry(x + dx[i], y + dy[i], z + dz[i]))return 0;
	}
	return 1;
}

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

int get(int x){
	int y = rng();
	y = abs(y);
	y %= x;
	++y;
	return y;
}

void skibidi(){
	int lx = 1, rx = n, ly = 1, ry = m;
	bool k = 1;
	ar<int, 2> c = {-1, -1};
	int val = -1;
	while(lx < rx || ly < ry){
		if(lx == rx)k = 1;
		if(ly == ry)k = 0;
		if(k){
			int mid = (lx + rx) / 2;
			int mx = -1, mi = -1;
			for(int i = ly;i <= ry;i++){
				if(mx < qry(mid, i, 1)){
					mx = qry(mid, i, 1);
					mi = i;
				}
			}
			if(check(mid, mi, 1)){
				lx = mid;
				ly = mi;
				break;
			}
			if(val > qry(mid, mi, 1)){
				if(c[0] < mid)rx = mid - 1;
				else lx = mid + 1;
			}else{
				c = {mid, mi};
				val = qry(mid, mi, 1);
				int l = qry(mid - 1, mi, 1), r = qry(mid + 1, mi, 1);
				if(l < r){
					lx = mid + 1;
				}else rx = mid - 1;
			}
		}else{
			int mid = (ly + ry) / 2;
			int my = -1, mi = -1;
			for(int i = lx;i <= rx;i++){
				if(my < qry(i, mid, 1)){
					my = qry(i, mid, 1);
					mi = i;
				}
			}
			if(check(mi, mid, 1)){
				ly = mid;
				lx = mi;
				break;
			}
			if(val > qry(mi, mid, 1)){
				if(c[1] < mid)ry = mid - 1;
				else ly = mid + 1;
			}else{
				c = {mi, mid};
				val = qry(mi, mid, 1);
				int l = qry(mi, mid - 1, 1), r = qry(mi, mid + 1, 1);
				if(l < r){
					ly = mid + 1;
				}else ry = mid - 1;
			}
		}
		k ^= 1;
	}

	cout<<"! "<<lx<<" "<<ly<<" "<<1<<endl;
	exit(0);
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int q;
	cin>>n>>m>>k>>q;
	if(k == 1)skibidi();
	int mx = -1, x, y, z;
	for(int i = 0;i < q / 2;i++){
		int a = get(n);
		int b = get(m);
		int c = get(k);
		if(qry(a, b, c) > mx){
			mx = qry(a, b, c);
			x = a, y = b, z = c;
		}
	}
	//cout<<x<<" "<<y<<" "<<z<<endl;
	while(all + 6 < q){
		if(check(x, y, z))break;
		int mx = -1, a, b, c;
		for(int i = 0;i < 6;i++){
			if(mx < qry(x + dx[i], y + dy[i], z + dz[i])){
				mx = qry(x + dx[i], y + dy[i], z + dz[i]);
				a = x + dx[i];
				b = y + dy[i];
				c = z + dz[i];
			}
		}
		x = a, y = b, z = c;
	}
	cout<<"! "<<x<<" "<<y<<" "<<z<<endl;
}	

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:135:11: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |   if(check(x, y, z))break;
      |      ~~~~~^~~~~~~~~
worm.cpp:135:11: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:135:11: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

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