제출 #1005295

#제출 시각아이디문제언어결과실행 시간메모리
1005295j_vdd16Worm Worries (BOI18_worm)C++17
77 / 100
1064 ms9868 KiB
#include <algorithm> #include <array> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef uint64_t u64; typedef int64_t i64; int a, b, c, q; void answer(int x, int y, int z) { cout << "! " << x << ' ' << y << ' ' << z << endl; } map<tuple<int, int, int>, int> results; inline int ask(int x, int y, int z) { if (x <= 0 || x > a || y <= 0 || y > b || z <= 0 || z > c) return 1; if (results.count({ x, y, z })) return results[{x, y, z}]; q--; if (q < 0) { answer(1, 1, 1); exit(0); } cout << "? " << x << ' ' << y << ' ' << z << endl; int res = x + y * z; cin >> res; results[{x, y, z}] = res; if (res == -1) { exit(0); } return res; } void solveGreedy() { int x = 1, y = 1, z = 1; while (true) { int val = ask(x, y, z); if (ask(x + 1, y, z) > val) x++; else if (ask(x - 1, y, z) > val) x--; else if (ask(x, y + 1, z) > val) y++; else if (ask(x, y - 1, z) > val) y--; else if (ask(x, y, z + 1) > val) z++; else if (ask(x, y, z - 1) > val) z--; else break; } answer(x, y, z); } inline int ask(const array<int, 3>& pos, const array<int, 3>& perm) { return ask(pos[perm[0]], pos[perm[1]], pos[perm[2]]); } array<int, 3> solve(ii bx, ii by, ii bz, int maxX, int maxY, int maxZ, array<int, 3> perm) { while (true) { int dx = bx.second - bx.first; int dy = by.second - by.first; int dz = bz.second - bz.first; if (dx <= 2 && dy <= 2 && dz <= 2) { array<int, 3> res = { maxX, maxY, maxZ }; return { res[perm[0]], res[perm[1]], res[perm[2]] }; } if (dy >= dx && dy >= dz) { swap(dx, dy); swap(bx, by); swap(maxX, maxY); if (perm[0] == 2) swap(perm[1], perm[2]); else if (perm[1] == 2) swap(perm[0], perm[2]); else swap(perm[0], perm[1]); } else if (dz >= dx && dz >= dy) { swap(dx, dz); swap(bx, bz); swap(maxX, maxZ); if (perm[0] == 1) swap(perm[1], perm[2]); else if (perm[1] == 1) swap(perm[0], perm[2]); else swap(perm[0], perm[1]); } int maxVal = ask({ maxX, maxY, maxZ }, perm); int x = bx.first + dx / 2; for (int y = by.first + 1; y < by.second; y++) { for (int z = bz.first + 1; z < bz.second; z++) { int val = ask({ x, y, z }, perm); if (val > maxVal) { maxVal = val; maxX = x; maxY = y; maxZ = z; } } } if (maxX != x) { if (maxX < x) bx.second = x; else bx.first = x; } else { int val1 = ask({ maxX - 1, maxY, maxZ }, perm); int val2 = ask({ maxX + 1, maxY, maxZ }, perm); if (maxVal >= val1 && maxVal >= val2) { array<int, 3> res = { maxX, maxY, maxZ }; return { res[perm[0]], res[perm[1]], res[perm[2]] }; } else if (val1 > maxVal) { bx.second = x; maxX -= 1; } else// if (val2 > maxVal) { bx.first = x; maxX += 1; } } } } signed main() { //ios::sync_with_stdio(0); //cin.tie(0); cin >> a >> b >> c >> q; if (a == 1 && b == 1 && c == 1) { answer(1, 1, 1); } else if (b == 1 && c == 1) { //f * f = (1 - f) //f^2 + f - 1 = 0 //f = (-1 + sqrt(5)) / 2 double f = (-1.0 + sqrt(5.0)) / 2.0; int l = 0, r = a + 1; int pos1 = -1, pos2 = -1; pos1 = l + (int)round(double(r - l) * (1 - f)); pos2 = l + (int)round(double(r - l) * f); while (true) { if (r == l) { answer(l, 1, 1); break; } else if (r - l == 1) { if (ask(l, 1, 1) > ask(r, 1, 1)) answer(l, 1, 1); else answer(r, 1, 1); break; } if (pos1 == -1) pos1 = l + (int)round(double(pos2 - l) * f); else if (pos2 == -1) pos2 = pos1 + (int)round(double(r - pos1) * (1 - f)); int val1 = ask(pos1, 1, 1); int val2 = ask(pos2, 1, 1); if (val1 > val2) { r = pos2; pos2 = pos1; pos1 = -1; } else { l = pos1; pos1 = pos2; pos2 = -1; } } } else if (a == 1 || b == 1 || c == 1 || (a <= 100 && b <= 100 && c <= 100)) { auto [x, y, z] = solve({ 0, a + 1 }, { 0, b + 1 }, { 0, c + 1 }, 1, 1, 1, { 0, 1, 2 }); answer(x, y, z); } else { solveGreedy(); } 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...