Submission #1098752

#TimeUsernameProblemLanguageResultExecution timeMemory
1098752vjudge1Worm Worries (BOI18_worm)C++17
0 / 100
1299 ms18216 KiB
#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;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int q;
	cin>>n>>m>>k>>q;
	map<ar<int, 3>, int> mp;
	for(int i = 0;i < q / 2;i++){
		int x = get(n);
		int y = get(m);
		int z = get(k);
		mp[{x, y, z}] = qry(x, y, z);
	}
	auto [x, y, z] = mp.rbegin()->first;
	//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:66:11: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |   if(check(x, y, z))break;
      |      ~~~~~^~~~~~~~~
worm.cpp:66:11: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:66:11: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...