Submission #779494

#TimeUsernameProblemLanguageResultExecution timeMemory
779494sadsaXylophone (JOI18_xylophone)C++17
0 / 100
6 ms348 KiB
#include "xylophone.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using ii = tuple<int, int>; using vii = vector<ii>; constexpr int iINF = numeric_limits<int>::max(); constexpr ll lINF = numeric_limits<ll>::max(); template <typename T> void DBG(T&& arg) { cerr << arg << '\n'; } template <typename T, typename... Ts> void DBG(T&& x, Ts&&... y) { cerr << x << ' '; DBG(y...); } static vector<vi> qcache; int q(int l, int r) { if (l > r) swap(l, r); int Q; if (l == r) Q = 0; else { Q = (qcache[l][r] != -1)? qcache[l][r]: (qcache[l][r] = query(l, r)); } DBG("query:", l, r, "V:", Q); return Q; } int find_one(int N) { DBG("find_one====================="); int l = 1; int r = N; int target = N-1; while (l != r) { DBG("l,r", l, r); if (r-l == 1) { if (q(l, N) == target) { r = l; } else { l = r; } break; } int mid = (l + r) / 2; DBG("mid", mid); if (q(mid, N) == target) { l = mid; } else { r = mid-1; } } return l; } int find_N(int index1, int N) { DBG("find_N==============="); int l = index1+1; int r = N; int target = N-1; while (l != r) { DBG("l,r", l, r); int mid = (l + r) / 2; DBG("mid", mid); if (q(index1, mid) == target) { r = mid; } else { l = mid+1; } } return l; } // finds a2 int get_next(int a0, int a1, int q02, int q12) { int a2; int q01 = abs(a1 - a0); if (q01 == q02) { DBG("WOOF"); // minmax didnt change => ai2 between ai0 and ai1 if (a0 < a1) a2 = a1 - q12; else a2 = a1 + q12; } else { DBG("MIAUW"); if (a0 < a1) { if (q12 >= q02) a2 = a1 - q12; else a2 = a1 + q12; } else { if (q12 == q02) a2 = a1 + q12; else if (q12 < q02) a2 = a1 - q12; else a2 = a1 + q12; } } return a2; } void solve(int N) { qcache.clear(); qcache.resize(N+1, vi(N+1, -1)); int index1 = find_one(N); DBG("index 1:", index1); int indexN = find_N(index1, N); DBG("index N:", indexN); vi ans(N+1); ans[index1] = 1; ans[indexN] = N; ans[index1+1] = 1+q(index1, index1+1); for (int i = index1; i+2 <= N; ++i) { DBG("starti", i); int i0=i; int i1=i+1; int i2=i+2; int q02 = q(i0, i2); int q12 = q(i1, i2); ans[i2] = get_next(ans[i0], ans[i1], q02, q12); DBG("next guess", ans[i0], ans[i1], ans[i2]); DBG("with info", q02, q12); } for (int i = index1+1; i-2 > 0; --i) { int i0 = i; int i1 = i-1; int i2 = i-2; int q02 = q(i2, i); int q12 = q(i2, i1); ans[i2] = get_next(ans[i0], ans[i1], q02, q12); } for (int i = 1; i <= N; ++i) { answer(i, ans[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...