Submission #717969

#	Time	Username	Problem	Language	Result	Execution time	Memory
717969		Charizard2021	Worm Worries (BOI18_worm)	C++17	100 / 100	1042 ms	288 KiB

worm

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};
int n, m, k, q;
map<int, int> val1;
int global_max = 0;
pair<int, int> maxval;
bool inBounds(int x, int y, int z){
    return (1 <= x && x <= n && 1 <= y && y <= m && 1 <= z && z <= k);
}
int query(int x, int y, int z){
	if(x <= 0 || x > n || y <= 0 || y > m || z <= 0 || z > k){
        return 0;
    }
    cout << "? " << x << " " << y << " " << z << "\n";
    cout.flush();
    int ans;
    cin >> ans;
    return ans;
}
int solve2(int x){
    if(x <= 0 || x > n){
        return 0;
    }
    if(val1.find(x) != val1.end()){
        return val1[x];
    }
    else{
        return val1[x] = query(x, 1, 1);
    }
}
void solve(int x1, int x2, int y1, int y2){
	if(x2 - x1 <= 2 && y2 - y1 <= 2){
		for(int i = x1; i <= x2; i++){
			for(int j = y1; j <= y2; j++){
				if(max({query(i - 1, j, 1), query(i, j - 1, 1), query(i + 1, j, 1), query(i, j + 1, 1)}) <= query(i, j, 1)){
					cout << "! " << i << " " << j << " " << 1 << "\n";
                    exit(0);
				}
			}
		}
        cout << "! " << maxval.first << " " << maxval.second << " " << 1 << "\n";
        exit(0);
	}
	if(x2 - x1 <= y2 - y1){
		int m = (y1 + y2) / 2;
		int maxval1 = -1;
        int maxvalidx = -1;
		for(int i = x1; i <= x2; i++){
			int v = query(i, m, 1);
			if(maxval1 < v){
				maxval1 = v;
				maxvalidx = i;
			}
		}
		if(maxval1 < global_max){
			if(maxval.second < m){
                solve(x1, x2, y1, m - 1);
            }
			else{
                solve(x1, x2, m + 1, y2);
            }
			return;
		}
		global_max = maxval1;
		maxval = make_pair(maxvalidx, m);
		if(maxval1 < query(maxvalidx, m+1, 1)){
			global_max = query(maxvalidx, m + 1, 1);
			maxval = make_pair(maxvalidx, m + 1);
			solve(x1, x2, m + 1, y2);
		}
		else if(maxval1 < query(maxvalidx, m-1, 1)){
			global_max = query(maxvalidx, m - 1, 1);
			maxval = make_pair(maxvalidx, m - 1);
			solve(x1, x2, y1, m - 1);
		}
		else{
            cout << "! " << maxvalidx << " " << m << " " << 1 << "\n";
            cout.flush();
            exit(0);
        }
	}
	else{
		int m = (x1 + x2) / 2;
		int maxval1 = -1, maxvalidx = -1;
		for(int i = y1; i <= y2; i++){
			int v = query(m, i, 1);
			if(maxval1 < v){
				maxval1 = v;
				maxvalidx = i;
			}
		}
		if(maxval1 < global_max){
			if(maxval.first < m){
                solve(x1, m - 1, y1, y2);
            }
			else{
                solve(m + 1, x2, y1, y2);
            }
			return;
		}
		global_max = maxval1;
		maxval = make_pair(m, maxvalidx);
		if(maxval1 < query(m + 1, maxvalidx, 1)){
			global_max = query(m + 1, maxvalidx, 1);
			maxval = make_pair(m + 1, maxvalidx);
			solve(m + 1, x2, y1, y2);
		}
		else if(maxval1 < query(m - 1, maxvalidx, 1)){
			global_max = query(m - 1, maxvalidx, 1);
			maxval = make_pair(m - 1, maxvalidx);
			solve(x1, m - 1, y1, y2);
		}
		else{
            cout << "! " << m << " " << maxvalidx << " " << 1 << "\n";
            cout.flush();
            exit(0);
        }
	}
}
int main(){
    cin >> n >> m >>  k >> q;
	if(m == 1){
		long double goldenRatio = (1 + sqrt(5)) / 2;
		int low = 1;
        int high = n;
		int x1 = -1;
        int x2 = -1;
		while(true){
			int m1 = round(low + (high - low) / (goldenRatio + 1));
			int m2 = round(low + (goldenRatio * (high - low)) / (goldenRatio + 1));
			if(~x1){
                m1 = x1;
            }
			if(~x2){
                m2 = x2;
            }
			if(m1 == m2){
                break;
            }
			if(solve2(m1) < solve2(m2)){
				low = m1;
				x1 = m2;
				x2 = -1;
			}
			else{
				high = m2;
				x1 = -1;
				x2 = m1;
			}
		}
		for(int i = low; i <= high; i++){
			if(solve2(i - 1) <= solve2(i) && solve2(i) >= solve2(i + 1)){
                cout << "! " << i << " " << 1 << " " << 1;
                cout.flush();
                exit(0);
            }
		}
	}
	if(k == 1){
		solve(1, n, 1, m);
	}
	int px = -1, py = -1, pz = -1, cur = 0;
	for(int i = 0; i < q/2; i++){
		int vx = rand() % n + 1, vy = rand() % m + 1, vz = rand() % k + 1;
		int val = query(vx, vy, vz);
		if(val > cur){
			cur = val;
			tie(px, py, pz) = make_tuple(vx, vy, vz);
		}
	}
	q = q - q / 2;
	while(q >= 6){
		int dir = -1;
		for(int i = 0; i < 6 ; i++){
			if(inBounds(px + dx[i], py + dy[i], pz + dz[i])){
				q--;
				int nval = query(px + dx[i], py + dy[i], pz + dz[i]);
				if(nval > cur){
					cur = nval;
					dir = i;
				}
			}
		}
		if(dir == -1){
            cout << "! " << px << " " << py << " " << pz << "\n";
            cout.flush();
            exit(0);
        }
		else{
			px += dx[dir];
			py += dy[dir];
			pz += dz[dir];
		}
	}
}

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