Submission #391721

#	Time	Username	Problem	Language	Result	Execution time	Memory
391721		Victor	Worm Worries (BOI18_worm)	C++17	10 / 100	280 ms	500192 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 a && a < x && b && b < y && c && c < z; }

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

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

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

    cin >> x >> y >> z >> q;
    grid.resize(x, vvi(y, vi(z)));

    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 - 1])
                n1 = arr[mid - 1];

            else {
                cout << "? " << mid - 1 << " 1 1" << endl;
                cin >> n1;
                arr[mid - 1] = n1;
            }

            if (arr[mid])
                n2 = arr[mid];

            else {
                cout << "? " << mid << " 1 1" << endl;
                cin >> n2;
                arr[mid] = n2;
            }

            if (n2 < n1) {
                hi = mid - 1;
                continue;
            }

            if (arr[mid + 1])
                n3 = arr[mid + 1];

            else {
                cout << "? " << mid + 1 << " 1 1" << endl;
                cin >> n3;
                arr[mid + 1] = n3;
            }

            if (n1 <= n2 && n3 <= n2) {
                cout << "! " << mid << " 1 1" << endl;
                break;

            } else if (n2 < n3)
                lo = mid + 1;
        }

    } else {
        int a = random() % x, b = random() % y, c = 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:108:33: warning: iteration 6 invokes undefined behavior [-Waggressive-loop-optimizations]
  108 |                 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)
......
  107 |             rep(l, 0, 9) {
      |                 ~~~~~~~                 
worm.cpp:107:13: note: in expansion of macro 'rep'
  107 |             rep(l, 0, 9) {
      |             ^~~
worm.cpp:116:43: warning: 'nc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |         cout<<"! "<<a+1<<' '<<b+1<<' '<<c+1<<endl;
      |                                           ^
worm.cpp:116:36: warning: 'nb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |         cout<<"! "<<a+1<<' '<<b+1<<' '<<c+1<<endl;
      |                                    ^~~
worm.cpp:116:26: warning: 'na' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |         cout<<"! "<<a+1<<' '<<b+1<<' '<<c+1<<endl;
      |                          ^~~

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