Submission #391740

#	Time	Username	Problem	Language	Result	Execution time	Memory
391740		Victor	Worm Worries (BOI18_worm)	C++17	0 / 100	916 ms	983428 KiB

worm

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(a, x) for (auto &a : x)
#define sz(a) a.size()
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

vector<vvi> grid;

int x, y, z, q;
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

bool valid(int a, int b, int c) { return 0 <= a && a < x && 0 <= b && b < y && 0 <= c && c < z; }

void question(int a, int b, int c) { cout << "? " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl; }

bool check(int a, int b, int c) {
    if (!grid[a][b][c]) {
        question(a, b, c);
        cin >> grid[a][b][c];
    }

    rep(i, 0, 9) {
        int na = a + dx[i], nb = b + dy[i], nc = c + dz[i];
        if (valid(na, nb, nc)) {
            if (!grid[na][nb][nc]) {
                question(na, nb, nc);
                cin >> grid[na][nb][nc];
            }
            if (grid[a][b][c] < grid[na][nb][nc]) return 0;
        }
    }
    return 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> x >> y >> z >> q;
    grid = vector<vvi>(x, vvi(y, vi(z, 0)));

    if (y == 1 && z == 1) {
        vi arr(x + 2, 0);
        arr[0] = arr[x + 1] = 1;
        int lo = 1, hi = x;

        while (1) {
            if (lo >= hi) {
                cout << "! " << lo << " 1 1" << endl;
                break;
            }

            int mid = (lo + hi) >> 1, n1, n2, n3;

            if (!arr[mid]) {
                cout << "? " << mid << " 1 1" << endl;
                cin >> arr[mid];
            }

            if(arr[lo]<arr[mid])lo=mid;
            else hi=mid;
        }

    } else {
        int a = (int)random() % x, b = (int)random() % y, c = (int)random() % z;
        while (!check(a, b, c)) {
            int mx = 0, na, nb, nc;
            rep(l, 0, 9) {
                int i = a + dx[l], j = b + dy[l], k = c + dz[l];
                if (valid(i, j, k) && mx < grid[i][j][k]) {
                    mx = grid[i][j][k];
                    na = i, nb = j, nc = k;
                }
            }
            a = na, b = nb, c = nc;
        }
        cout << "! " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
    }
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:60:39: warning: unused variable 'n1' [-Wunused-variable]
   60 |             int mid = (lo + hi) >> 1, n1, n2, n3;
      |                                       ^~
worm.cpp:60:43: warning: unused variable 'n2' [-Wunused-variable]
   60 |             int mid = (lo + hi) >> 1, n1, n2, n3;
      |                                           ^~
worm.cpp:60:47: warning: unused variable 'n3' [-Wunused-variable]
   60 |             int mid = (lo + hi) >> 1, n1, n2, n3;
      |                                               ^~
worm.cpp:76:33: warning: iteration 6 invokes undefined behavior [-Waggressive-loop-optimizations]
   76 |                 int i = a + dx[l], j = b + dy[l], k = c + dz[l];
      |                             ~~~~^
worm.cpp:3:40: note: within this loop
    3 | #define rep(i, a, b) for (int i = a; i < b; ++i)
......
   75 |             rep(l, 0, 9) {
      |                 ~~~~~~~                 
worm.cpp:75:13: note: in expansion of macro 'rep'
   75 |             rep(l, 0, 9) {
      |             ^~~
worm.cpp:84:61: warning: 'nc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         cout << "! " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
      |                                                             ^
worm.cpp:84:50: warning: 'nb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         cout << "! " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
      |                                                  ^~~
worm.cpp:84:34: warning: 'na' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         cout << "! " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
      |                                  ^~~

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