Submission #939344

#	Time	Username	Problem	Language	Result	Execution time	Memory
939344		WendidIask0303	Worm Worries (BOI18_worm)	C++17	Compilation error	0 ms	0 KiB

worm

#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 (stderr)

worm.cpp:1:10: fatal error: worm.h: No such file or directory
    1 | #include "worm.h"
      |          ^~~~~~~~
compilation terminated.