#include "worm.h"
#include <chrono>
#include <random>
#include <algorithm>
#include <unordered_map>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k, q;
unordered_map<int, unordered_map<int, unordered_map<int, int>>> box;
int query(int x, int y, int z){
if (x < 1 || x > n || y < 1 || y > m || z < 1 || z > k) return 0;
int &v = box[x][y][z];
if (v == 0) v = Query(x, y, z);
return v;
}
void task1(){
int l = 1;
int r = n;
int m1 = 0.618*l+0.382*r;
int m2 = 0.382*l+0.618*r;
while (l+5<r) {
if (m1 >= m2) {
m1 = 0.618*l+0.382*r;
m2 = 0.382*l+0.618*r;
if (m1 >= m2) break;
}
if (query(m1, 1, 1) < query(m2, 1, 1)){
l = m1+1;
m1 = m2;
m2 = 0.382*l+0.618*r;
}
else {
r = m2-1;
m2 = m1;
m1 = 0.618*l+0.382*r;
}
}
for (int i=l; i<=r; i++){
if (query(i, 1, 1) >= max(query(i-1, 1, 1), query(i+1, 1, 1))) Guess(i, 1, 1);
}
}
void task2(){
int x1 = 1;
int x2 = n;
int y1 = 1;
int y2 = m;
pair<int, int> b = {0, 0};
while (x1 != x2 || y1 != y2){
if (x1 != x2){
int mid = (x1+x2)/2;
for (int i=y1; i<=y2; i++){
if (query(mid, i, 1) > query(b.first, b.second, 1)) b = {mid, i};
}
if (b.first < mid) x2 = mid-1;
else if (b.first > mid) x1 = mid+1;
else if (query(mid-1, b.second, 1) > query(mid, b.second, 1)) x2 = mid-1;
else if (query(mid+1, b.second, 1) > query(mid, b.second, 1)) x1 = mid+1;
else Guess(mid, b.second, 1);
}
if (y1 != y2){
int mid = (y1+y2)/2;
for (int i=x1; i<=x2; i++){
if (query(i, mid, 1) > query(b.first, b.second, 1)) b = {i, mid};
}
if (b.second < mid) y2 = mid-1;
else if (b.second > mid) y1 = mid+1;
else if (query(b.first, mid-1, 1) > query(b.first, mid, 1)) y2 = mid-1;
else if (query(b.first, mid+1, 1) > query(b.first, mid, 1)) y1 = mid+1;
else Guess(b.first, mid, 1);
}
}
Guess(x1, y1, 1);
}
void task3(){
int X, Y, Z;
int mx = 0;
for(int i=1; i<=q/2; i++){
int x = rng()%n+1;
int y = rng()%m+1;
int z = rng()%k+1;
if (query(x, y, z) > mx){
mx = query(x, y, z);
X = x;
Y = y;
Z = z;
}
}
while (query(X, Y, Z) < max({query(X-1, Y, Z), query(X+1, Y, Z), query(X, Y-1, Z), query(X, Y+1, Z), query(X, Y, Z-1), query(X, Y, Z+1)})){
if (query(X+1, Y, Z) > query(X, Y, Z)) X++;
else if (query(X-1, Y, Z) > query(X, Y, Z)) X--;
else if (query(X, Y+1, Z) > query(X, Y, Z)) Y++;
else if (query(X, Y-1, Z) > query(X, Y, Z)) Y--;
else if (query(X, Y, Z+1) > query(X, Y, Z)) Z++;
else if (query(X, Y, Z-1) > query(X, Y, Z)) Z--;
}
Guess(X, Y, Z);
}
void Init(int N, int M, int K, int Q){
n = N;
m = M;
k = K;
q = Q;
if (m == 1 && k == 1) task1();
else if (k == 1) task2();
else task3();
}
Compilation message
worm.cpp:1:10: fatal error: worm.h: No such file or directory
1 | #include "worm.h"
| ^~~~~~~~
compilation terminated.
