Submission #633808

#TimeUsernameProblemLanguageResultExecution timeMemory
633808Saeed_247Xylophone (JOI18_xylophone)C++14
47 / 100
85 ms548 KiB
#include "xylophone.h" #include <bits/stdc++.h> using namespace std; static int A[5010]; int pos[5050]; void solve(int n) { int lo = 1, hi = n; while (hi - lo > 1) { int mid = (lo + hi) / 2; if (query(mid, n) == n - 1) { lo = mid; } else { hi = mid; } } A[lo] = 1; pos[1] = lo; if (lo > 1) { A[lo - 1] = query(lo - 1, lo) + 1; pos[A[lo - 1]] = lo - 1; } A[lo + 1] = query(lo, lo + 1) + 1; pos[A[lo + 1]] = lo + 1; for (int i = lo - 2; i >= 1; i--) { int diff = query(i, i + 1); bool a = (pos[min(A[i + 1] + diff, n + 1)] == 0), b = (pos[min(A[i + 1] - diff, 0)] == 0); if (a && b) { int x = query(i, i + 2); if (max({A[i + 1] + diff, A[i + 1], A[i + 2]}) - min({A[i + 1] + diff, A[i + 1], A[i + 2]}) == x) { A[i] = A[i + 1] + diff; } else { A[i] = A[i + 1] - diff; } } else if (a) A[i] = A[i + 1] + diff; else A[i] = A[i + 1] - diff; pos[A[i]] = i; } for (int i = lo + 2; i <= n; i++) { int diff = query(i - 1, i); bool a = (pos[min(A[i - 1] + diff, n + 1)] == 0), b = (pos[min(A[i - 1] - diff, 0)] == 0); if (a && b) { int x = query(i - 2, i); if (max({A[i - 1] + diff, A[i - 1], A[i - 2]}) - min({A[i - 1] + diff, A[i - 1], A[i - 2]}) == x) { A[i] = A[i - 1] + diff; } else { A[i] = A[i - 1] - diff; } } else if (a) A[i] = A[i - 1] + diff; else A[i] = A[i - 1] - diff; pos[A[i]] = i; } for (int i = 1; i <= n; i++) { answer(i, A[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...