Submission #773355

#TimeUsernameProblemLanguageResultExecution timeMemory
773355rxlfd314A Difficult(y) Choice (BOI21_books)C++17
100 / 100
1 ms1064 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; using ll = long long; void solve(int N, int K, ll A, int S) { ll a[N+1]; memset(a, -1, sizeof(a)); auto ask = [&](int i) { return a[i] = a[i] < 0 ? skim(i) : a[i]; }; ll sum = 0; for (int i = 1; i < K; i++) { sum += ask(i); } if (sum >= A) { if (sum + ask(K) > A+A) { impossible(); } vector<int> ans(K); iota(ans.begin(), ans.end(), 1); answer(ans); } int lo = K, hi = N+1; while (lo < hi) { int mid = lo + hi >> 1; ask(mid) + sum < A ? lo = mid + 1 : hi = mid; } if (lo <= N && ask(lo) + sum <= A+A) { vector<int> ans(K); iota(ans.begin(), ans.end(), 1); ans[K-1] = lo; answer(ans); } if (lo-- == K) { impossible(); } vector<int> lft(K-1), rht = {lo}; sum += ask(lo); iota(lft.begin(), lft.end(), 1); reverse(lft.begin(), lft.end()); for (int i = lo-1; i > max(K-1, lo-K) && sum < A; i--) { sum += ask(i) - ask(lft.back()); lft.pop_back(); rht.push_back(i); } if (sum < A) { impossible(); } for (int i : rht) { lft.push_back(i); } answer(lft); }

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = lo + hi >> 1;
      |             ~~~^~~~
#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...