Submission #815373

#TimeUsernameProblemLanguageResultExecution timeMemory
815373PikachuXylophone (JOI18_xylophone)C++17
100 / 100
64 ms440 KiB
#include <bits/stdc++.h> #include "xylophone.h" using namespace std; const int maxn = 5010; int a[maxn]; bool done[maxn]; void solve(int n) { int l = 1; int r = n; int dak = 1; while (l <= r) { int mid = (l + r) / 2; if (query(mid, n) == n - 1) dak = mid, l = mid + 1; else r = mid - 1; } l = dak; answer(l, 1); a[l] = 1; done[1] = true; for (int i = l - 1; i >= 1; i--) { int x = query(i, i + 1); int ans = -1; if (a[i + 1] - x <= 0 || done[a[i + 1] - x]) ans = a[i + 1] + x; if (a[i + 1] + x > n || done[a[i + 1] + x]) ans = a[i + 1] - x; if (ans == -1) { if (max({a[i + 1] + x, a[i + 1], a[i + 2]}) - min({a[i + 1] + x, a[i + 1], a[i + 2]}) != query(i, i + 2)) ans = a[i + 1] - x; else ans = a[i + 1] + x; } a[i] = ans; done[ans] = true; answer(i, a[i]); } for (int i = l + 1; i <= n; i++) { int x = query(i - 1, i); int ans = -1; if (a[i - 1] - x <= 0 || done[a[i - 1] - x]) ans = a[i - 1] + x; if (a[i - 1] + x > n || done[a[i - 1] + x]) ans = a[i - 1] - x; if (ans == -1) { if (max({a[i - 1] + x, a[i - 1], a[i - 2]}) - min({a[i - 1] + x, a[i - 1], a[i - 2]}) != query(i - 2, i)) ans = a[i - 1] - x; else ans = a[i - 1] + x; } a[i] = ans; done[ans] = true; answer(i, a[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...