Submission #717963

#	Time	Username	Problem	Language	Result	Execution time	Memory
717963		Charizard2021	Worm Worries (BOI18_worm)	C++17	49 / 100	852 ms	4176 KiB

worm

#include<bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, m, k, maxq;
long double goldRatio = (1 + sqrt(5))/2;
int value(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 << endl;
    cout.flush();
	int ans;
	cin >> ans;
	if (ans == -1){
        exit(0);
    }
	return ans;
}
int ans9[N];
int solve(int a, int b){
    if(a == b){
        return a;
    }
    int mid = floor(((long double)a * (goldRatio - 1) + (long double)b * (2 - goldRatio)));
    int ans;
    if(ans9[mid] == -1){
        cout << "? " << mid << " " << 1 << " " << 1 << endl;
        cout.flush();
        cin >> ans;
    }
    else{
        ans = ans9[mid];
    }
    ans9[mid] = ans;
    int ans2;
    if(ans9[mid + 1] == -1){
        cout << "? " << mid + 1 << " " << 1 << " " << 1 << endl;
        cout.flush();
        cin >> ans2;
    }
    else{
        ans2 = ans9[mid + 1];
    }
    ans9[mid + 1] = ans2;
    if(ans >= ans2){
        return solve(a, mid);
    }
    else{
        return solve(mid + 1, b);
    }
}
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
int main(){
	cin >> n >> m >> k >> maxq;
    if(m != 1 || k != 1){
        int samples = maxq / 2;
        int record = 0;
        int x = -1, y = -1, z = -1;
        for(int i = 0; i < samples; i++){
            int a = 1 + rand() % n;
            int b = 1 + rand() % m;
            int c = 1 + rand() % k;
            int res = value(a, b, c);
            if(res > record){
                record = res;
                x = a, y = b, z = c;
            }
        }
        int walked = 0;
        vector<bool> tried(6, false);
        while (true) {
            int left = 0;
            for(int i = 0; i < 6; i++){
                left += (int)!tried[i];
            }
            if(left == 0){
                cout << "! " << x << ' ' << y << ' ' << z << endl;
                return 0;
            }
            int r = rand() % left;
            for(int i = 0; i < 6; i++){
                if(!tried[i]){
                    if(r == 0){
                        int x1 = x + dx[i];
                        int	y1 = y + dy[i];
                        int	z1 = z + dz[i];
                        int res = value(x1, y1, z1);
                        if(res > record){
                            record = res;
                            x = x1;
                            y = y1;
                            z = z1;
                            for(int j = 0; j < 6; j++){
                                tried[j] = false;
                            }
                            tried[i ^ 1] = true;
                            walked++;
                            break;
                        }
                        else {
                            tried[i] = true;
                            break;
                        }
                    }
                    r--;
                }
            }
        }
    }
    else{
        for(int i = 1; i <= N; i++){
            ans9[i] = -1;
        }
        cout << solve(1, n) << " " << 1 << " " << 1 << "\n";
    }
}
/*1 3 5 5 1 313 12 3*/

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:114:21: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations]
  114 |             ans9[i] = -1;
      |             ~~~~~~~~^~~~
worm.cpp:113:26: note: within this loop
  113 |         for(int i = 1; i <= N; i++){
      |                        ~~^~~~
worm.cpp:114:21: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [4000004, 4000007] is out of the bounds [0, 4000004] of object 'ans9' with type 'int [1000001]' [-Warray-bounds]
  114 |             ans9[i] = -1;
      |             ~~~~~~~~^~~~
worm.cpp:19:5: note: 'ans9' declared here
   19 | int ans9[N];
      |     ^~~~

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