Submission #951511

#TimeUsernameProblemLanguageResultExecution timeMemory
951511kilkuwuXylophone (JOI18_xylophone)C++17
100 / 100
48 ms744 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "xylophone.h" #else void solve(int N); int query(int s, int t); void answer(int i, int a); static const int __N_MAX = 5000; static const int __Q_MAX = 10000; static int __N; static int __A[__N_MAX]; static bool __used[__N_MAX]; static int __query_c; static int __answer_c; int query(int s, int t) { if(__query_c >= __Q_MAX) { printf("Wrong Answer\n"); exit(0); } __query_c++; if(!(1 <= s && s <= t && t <= __N)) { printf("Wrong Answer\n"); exit(0); } int mx = 0, mn = __N + 1; for(int i = s - 1; i < t; i++) { if(mx < __A[i]) { mx = __A[i]; } if(mn > __A[i]) { mn = __A[i]; } } return mx - mn; } void answer(int i, int a) { __answer_c++; if(!(1 <= i && i <= __N)) { printf("Wrong Answer\n"); exit(0); } if(!(1 <= a && a <= __N)) { printf("Wrong Answer\n"); exit(0); } if(__used[i - 1]) { printf("Wrong Answer\n"); exit(0); } if(a != __A[i - 1]) { printf("Wrong Answer\n"); exit(0); } __used[i - 1] = true; } int main() { __query_c = 0; __answer_c = 0; if(scanf("%d", &__N) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } for(int i = 0; i < __N; i++) { if(scanf("%d", __A + i) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } __used[i] = false; } solve(__N); if(!(__answer_c == __N)) { printf("Wrong Answer\n"); exit(0); } printf("Accepted : %d\n", __query_c); } #endif #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif void solve(int N) { int lb = 1, rb = N; while (lb < rb) { int mid = (lb + rb + 1) / 2; if (query(mid, N) != N - 1) { rb = mid - 1; } else { lb = mid; } } // we know A[lb] == 1 // we will know lb + 1 std::vector<int> filled(N + 1, 0); std::vector<int> A(N + 1), D(N + 1, -1); A[lb] = 1; filled[1] = 1; if (lb + 1 <= N) { D[lb + 1] = query(lb, lb + 1); A[lb + 1] = A[lb] + D[lb + 1]; filled[A[lb + 1]] = 1; } if (lb - 1 >= 1) { D[lb - 1] = query(lb - 1, lb); A[lb - 1] = A[lb] + D[lb - 1]; filled[A[lb - 1]] = 1; } for (int L = lb - 2; L >= 1; L--) { D[L] = query(L, L + 1); A[L] = A[L + 1]; int vp = A[L] + D[L]; int vm = A[L] - D[L]; if (vp > N || filled[vp]) { A[L] = vm; } else if (vm < 1 || filled[vm]) { A[L] = vp; } else { int tie = query(L, L + 2); if (tie == D[L] + D[L + 1]) { A[L] = (A[L + 1] < A[L + 2]) ? vm : vp; } else { A[L] = (A[L + 1] < A[L + 2]) ? vp : vm; } } filled[A[L]] = 1; } for (int R = lb + 2; R <= N; R++) { D[R] = query(R - 1, R); A[R] = A[R - 1]; int vp = A[R] + D[R]; int vm = A[R] - D[R]; if (vp > N || filled[vp]) { A[R] = vm; } else if (vm < 1 || filled[vm]) { A[R] = vp; } else { int tie = query(R - 2, R); if (tie == D[R] + D[R - 1]) { A[R] = (A[R - 2] < A[R - 1]) ? vp : vm; } else { A[R] = (A[R - 2] < A[R - 1]) ? vm : vp; } } filled[A[R]] = 1; } 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...