Submission #590494

#TimeUsernameProblemLanguageResultExecution timeMemory
590494messiuuuuuXylophone (JOI18_xylophone)C++14
100 / 100
66 ms452 KiB
#include<bits/stdc++.h> #include <xylophone.h> #define task "main" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 1e5 + 5; const ll INF = 1e18 + 5; int res[MAXN]; bool ava[MAXN]; void solve(int n) { int l = 1, r = n; while (l <= r) { int mid = (l + r) / 2; if (query(mid, n) == n - 1) l = mid + 1; else r = mid - 1; } res[r] = 1; ava[1] = 1; if (r < n) { res[r + 1] = 1 + query(r, r + 1); ava[res[r + 1]] = 1; for (int i = r + 2; i <= n; i++) { int b = query(i - 1, i); if (res[i - 1] + b > n || ava[res[i - 1] + b]) { res[i] = res[i - 1] - b; ava[res[i]] = 1; continue; } if (res[i - 1] - b < 1 || ava[res[i - 1] - b]) { res[i] = res[i - 1] + b; ava[res[i]] = 1; continue; } int a = query(i - 2, i); if (res[i - 1] > res[i - 2]) { if (res[i - 1] + b == a + res[i - 2]) res[i] = res[i - 1] + b; else res[i] = res[i - 1] - b; } else { if (res[i - 2] - a == res[i - 1] - b) { res[i] = res[i - 1] - b; } else { res[i] = res[i - 1] + b; } } ava[res[i]] = 1; } } if (r > 1) { res[r - 1] = 1 + query(r - 1, r); ava[res[r - 1]] = true; for (int i = r - 2; i >= 1; -- i) { int b = query(i, i + 1); if (res[i + 1] + b > n || ava[res[i + 1] + b]) { res[i] = res[i + 1] - b; ava[res[i]] = true; continue; } if (res[i + 1] - b < 1 || ava[res[i + 1] - b]) { res[i] = res[i + 1] + b; ava[res[i]] = true; continue; } int a = query(i, i + 2); if (res[i + 2] > res[i + 1]) { if (res[i + 1] - b == res[i + 2] - a) { res[i] = res[i + 1] - b; } else { res[i] = res[i + 1] + b; } } else { if (res[i + 1] + b == res[i + 2] + a) { res[i] = res[i + 1] + b; } else { res[i] = res[i + 1] - b; } } } } for (int i = 1; i <= n; ++ i) { answer(i, res[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...