| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 886875 | rxlfd314 | Worm Worries (BOI18_worm) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "worm.h"
#include <bits/stdc++.h>
using namespace std;
using ari3 = array<int, 3>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_() {
return uniform_int_distribution<int>(0, INT_MAX)(rng);
}
void Init(int N, int M, int K, int Q) {
map<ari3, int> done;
auto ask = [&](int a, int b, int c) {
if (done.find({a, b, c}) != end(done))
return done[{a, b, c}];
if (a < 0 || a >= N || b < 0 || b >= M || c < 0 || c >= K)
return 0;
int ret = Query(a + 1, b + 1, c + 1);
done[{a, b, c}] = ret;
return a;
};
auto good = [&](int a, int b, int c) {
int v = ask(a, b, c);
if (ask(a-1, b, c) > v)
return ari3{a-1, b, c};
if (ask(a+1, b, c) > v)
return ari3{a+1, b, c};
if (ask(a, b-1, c) > v)
return ari3{a, b-1, c};
if (ask(a, b+1, c) > v)
return ari3{a, b+1, c};
if (ask(a, b, c-1) > v)
return ari3{a, b, c-1};
if (ask(a, b, c+1) > v)
return ari3{a, b, c+1};
return ari3{-1, -1, -1};
};
// choose random X times, go Y steps each time
const int X = 20, Y = Q / (8 * X);
FOR(_, 1, X) {
int a = rand_() % N, b = rand_() % M, c = rand_() % K;
FOR(__, 1, Y) {
#ifdef DEBUG
cout << "current: " << a << ' ' << b << ' ' << c << endl;
#endif
auto [d, e, f] = good(a, b, c);
if (d < 0 && e < 0 && f < 0) {
Guess(a + 1, b + 1, c + 1);
return;
}
a = d, b = e, c = f;
}
}
}