Submission #729207

#TimeUsernameProblemLanguageResultExecution timeMemory
729207NeroZeinA Difficult(y) Choice (BOI21_books)C++17
100 / 100
1 ms336 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; const int N = 1000005; long long a[N]; int L[N], R[N]; void solve(int N_, int K_, long long A, int S_) { // TODO implement this function long long s = 0; int k = K_; int n = N_; for (int i = 1; i <= k; ++i) { a[i] = skim(i); s += a[i]; L[i] = i; } L[k + 1] = n + 1; if (s > 2LL * A) { impossible(); return; } for (int i = k; i >= 0; --i) { if (!i) { impossible(); return; } R[i] = L[i + 1] - 1; if (!a[R[i]]) { a[R[i]] = skim(R[i]); } if (s - a[i] + a[R[i]] <= 2LL * A) { L[i] = R[i]; } while (L[i] < R[i]) { int mid = (L[i] + R[i] + 1) >> 1LL; if (!a[mid]) { a[mid] = skim(mid); } if (s - a[i] + a[mid] > 2LL * A) { R[i] = mid - 1; } else { L[i] = mid; } } s -= a[i]; s += a[L[i]]; if (s >= A) { break; } } vector<int> v; for (int i = 1; i <= k; ++i) { v.push_back(L[i]); } answer(v); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...