제출 #108824

#제출 시각아이디문제언어결과실행 시간메모리
108824atoizWorm Worries (BOI18_worm)C++14
59 / 100
1304 ms502576 KiB
#include <iostream> #include <vector> #include <cstring> #include <random> #include <algorithm> #include <chrono> using namespace std; namespace Subtask1D { int N; vector<int> A; int get(int i) { if (i <= 0 || i > N) return 0; if (A[i]) return A[i]; cout << "? " << i << " 1 1" << endl; cin >> A[i]; return A[i]; } void run(int _N, int _Q) { N = _N; A.assign(N+1, 0); int l = 1, r = N; while (l < r) { int m = (l + r) >> 1; if (get(m) < get(m + 1)) { l = m + 1; } else r = m; } cout << "! " << l << " 1 1" << endl; } } namespace Subtask3D { const int di[6] = {-1, 1, 0, 0, 0, 0}, dj[6] = {0, 0, -1, 1, 0, 0}, dk[6] = {0, 0, 0, 0, -1, 1}; int dd[6] = {0, 1, 2, 3, 4, 5}; vector< vector< vector<int> > > A; int N, M, K, Q; mt19937 rng(chrono::system_clock().now().time_since_epoch().count()); uniform_int_distribution<int> rnd(1, 1e9); int rd(int l, int r) { return l + rnd(rng) % (r - l + 1); } int get(int i, int j, int k) { if (0 >= i || i > N || 0 >= j || j > M || 0 >= k || k > K) return 0; if (A[i][j][k]) return A[i][j][k]; cout << "? " << i << ' ' << j << ' ' << k << endl; cin >> A[i][j][k]; return A[i][j][k]; } void run(int _N, int _M, int _K, int _Q) { N = _N, M = _M, K = _K, Q = _Q; A.assign(N+1, vector< vector<int> >(M+1, vector<int>(K+1, 0))); int i0 = 0, j0 = 0, k0 = 0; for (int _ = 0; _ < Q * 2 / 3; ++_) { int i = rd(1, N), j = rd(1, M), k = rd(1, K); if (get(i0, j0, k0) < get(i, j, k)) i0 = i, j0 = j, k0 = k; } while (true) { shuffle(dd, dd + 6, rng); int d = 0; for (; d < 6; ++d) { int i = i0 + di[dd[d]], j = j0 + dj[dd[d]], k = k0 + dk[dd[d]]; if (get(i0, j0, k0) < get(i, j, k)) { i0 = i, j0 = j, k0 = k; break; } } if (d == 6) { cout << "! " << i0 << ' ' << j0 << ' ' << k0 << endl; return; } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M, K, Q; cin >> N >> M >> K >> Q; if (K > 1 || M > 1) Subtask3D::run(N, M, K, Q); else Subtask1D::run(N, Q); }
#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...