Submission #1263861

#TimeUsernameProblemLanguageResultExecution timeMemory
1263861niepamietamhaslaWorm Worries (BOI18_worm)C++20
100 / 100
216 ms4200 KiB
#include <bits/stdc++.h> #define pii pair<int,int> using namespace std; typedef long long ll; typedef long double ld; int n, m, k, q; map<ll, int> pamiec; vector<pair<int,pii>> roza = {{0,{0,1}},{0,{0,-1}},{0,{1,0}},{0,{-1,0}},{1,{0,0}},{-1,{0,0}}}; int pars(int x, int y, int z){ if(x < 1 or x > n or y < 1 or y > m or z < 1 or z > k) return 0; ll G = x - 1 + (y-1) * n + (z-1) *n*m; if(pamiec.find(G) != pamiec.end()) return pamiec[G]; cout << "? " << x << " " << y << " " << z << "\n"; cin >> pamiec[G]; return pamiec[G]; } pair<int, pii> synowie(int x, int y, int z){ int curr = pars(x, y, z); for(auto u : roza){ int x2 = x + u.first; int y2 = y + u.second.first; int z2 = z + u.second.second; if(pars(x2,y2,z2) > curr) return {x2, {y2,z2}}; } return {-1, {-1, -1}}; } int znajdz1d(int a, int b, pii znane){ if(a > b) return -1; if(a == b) return a; if(b - a + 1 <= 5){ for(int i = a; i <= b; ++i){ int lewo = pars(i-1, 1, 1); int curr = pars(i, 1, 1); int prawo = pars(i+1, 1, 1); if(curr >= lewo and curr >= prawo){ return i; } } } pii split = znane; if(split.first == -1){ split.first = (0.618 * (ld)a + 0.382 * (ld)b); } if(split.second == -1){ split.second = ((ld)0.382 * (ld)a + (ld)0.618 * (ld)b); } if(split.first <= a){ split.first = a + 1; } if(split.second >= b){ split.second = b-1; } if(split.first == split.second){ if(split.second + 1 != b) split.second++; else split.first--; } if(split.first >= split.second) swap(split.first, split.second); int L1 = pars(split.first, 1, 1); int L2 = pars(split.second, 1, 1); // cout << a << " " << b << " ab\n"; // cout << split.first << " " << split.second << " spl\n"; // cout << L1 << " " << L2 << " L\n"; if(L1 >= L2){ return znajdz1d(a, split.second - 1, {-1, split.first}); } else{ return znajdz1d(split.first + 1, b, {split.second, -1}); } // if(a == b) return a; // if(b - a + 1 <= 3){ // for(int i = a; i <= b; ++i){ // int lewo = pars(i-1, 1, 1); // int curr = pars(i, 1, 1); // int prawo = pars(i+1, 1, 1); // if(curr >= lewo and curr >= prawo){ // return i; // } // } // } // ll mid = (a + b) / 2; // ll nxt = mid + 1; // int L1 = pars(mid, 1, 1); // int L2 = pars(nxt, 1, 1); // if(L1 >= L2){ // return znajdz1d(a, mid, {-1,-1}); // } // else{ // return znajdz1d(nxt, b, {-1, -1}); // } } bool spr(pii x){ int i = x.first; int j = x.second; int lew = pars(i,j-1,1); int gor = pars(i+1,j,1); int pra = pars(i,j+1,1); int dol = pars(i-1,j,1); int mid = pars(i,j,1); if(mid >= lew and mid >= pra and mid >= gor and mid >= dol) return true; return false; } pii znajdz2d(pii lewydolny, pii prawygorny, int prevmax, pii prevwhere, int kierunek){ if(abs(lewydolny.first - prawygorny.first) * abs(lewydolny.second - prawygorny.second) <= 50){ for(int i = lewydolny.first; i <= prawygorny.first; ++i){ for(int j = lewydolny.second; j <= prawygorny.second; ++j){ if(spr({i,j})) return {i, j}; } } return {-1, -1}; } if(kierunek == 0){ int mid = (lewydolny.second + prawygorny.second) / 2; int mx = -1; pii where; for(int i = lewydolny.first; i <= prawygorny.first; ++i){ int T = pars(i, mid, 1); if(T >= mx){ mx = T; where = {i, mid}; } } if(spr(where)) return where; int L1 = pars(where.first, where.second - 1, 1); int L2 = pars(where.first, where.second + 1, 1); if(max(L1, L2) >= prevmax){ if(L1 >= L2){ return znajdz2d(lewydolny, {prawygorny.first, mid - 1}, L1, {where.first - 1, where.second}, kierunek ^ 1); } else{ return znajdz2d({lewydolny.first, mid + 1}, prawygorny, L2, {where.first + 1, where.second}, kierunek ^ 1); } } else{ if(prevwhere.second > mid){ return znajdz2d({lewydolny.first, mid + 1}, prawygorny, prevmax, prevwhere, kierunek ^ 1); } else{ return znajdz2d(lewydolny, {prawygorny.first, mid - 1}, prevmax, prevwhere, kierunek ^ 1); } } } else{ int mid = (lewydolny.first + prawygorny.first) / 2; int mx = -1; pii where; for(int j = lewydolny.second; j <= prawygorny.second; ++j){ int T = pars(mid, j, 1); if(T > mx){ mx = T; where = {mid, j}; } } if(spr(where)) return where; int L1 = pars(where.first - 1, where.second, 1); int L2 = pars(where.first + 1, where.second, 1); if(max(L1, L2) >= prevmax){ if(L1 >= L2){ return znajdz2d(lewydolny, {mid - 1, prawygorny.second}, L1, {where.first - 1, where.second}, kierunek ^ 1); } else{ return znajdz2d({mid + 1, lewydolny.second}, prawygorny, L2, {where.first + 1, where.second}, kierunek ^ 1); } } else{ if(prevwhere.first > mid){ return znajdz2d({mid + 1, lewydolny.second}, prawygorny, prevmax, prevwhere, kierunek ^ 1); } else{ return znajdz2d(lewydolny, {mid - 1, prawygorny.second}, prevmax, prevwhere, kierunek ^ 1); } } } } int main(){ cin >> n >> m >> k >> q; if(m == 1 and k == 1 and q <= 35){ int x = znajdz1d(1, n, {-1, -1}); cout << "! " << x << " " << 1 << " " << 1 << "\n"; } else if(k == 1 and q <= 3500){ pii X = znajdz2d({1, 1}, {n, n}, 0, {-1, -1}, 0); cout << "! " << X.first << " " << X.second << " " << 1 << "\n"; } else{ srand(time(NULL)); pair<int,pair<int,pii>> naj = {-1, {-1, {-1, -1}}}; for(int i = 0; i < q/3; ++i){ int x = rand() % n + 1; int y = rand() % m + 1; int z = rand() % k + 1; naj = max(naj, {pars(x,y,z), {x, {y, z}}}); } int x = naj.second.first; int y = naj.second.second.first; int z = naj.second.second.second; while(true){ pair<int,pii> nxt = synowie(x, y, z); if(nxt.first == -1) break; x = nxt.first; y = nxt.second.first; z = nxt.second.second; } cout << "! " << x << " " << y << " " << z << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...