Submission #554608

#TimeUsernameProblemLanguageResultExecution timeMemory
554608yoavLA Difficult(y) Choice (BOI21_books)C++14
100 / 100
2 ms1064 KiB
#include <bits/stdc++.h> #include "books.h" #define pr(x) cout << x << endl #define wpr(x) cout << #x << ": " << x << endl #define rep(i, s, e) for(ll i = s; i < e ; i++) #define upmin(a, b) (a) = min((ll)a, (ll)b) using namespace std; using ll = long long; using vll = vector<ll>; using vi = vector<int>; // // --- Sample implementation for the task books --- // // To compile this program with the sample grader, place: // books.h books_sample.cpp sample_grader.cpp // in a single folder and run: // g++ books_sample.cpp sample_grader.cpp // in this folder. // vll a; ll n, k, A, s; ll leftmostBig; ll arr(ll i) { if(a[i] == -1) a[i] = skim(i+1); return a[i]; } // Finds the left-most index whose value is at least A void find_leftmost_big() { ll l = 0, h = n-1, m; leftmostBig = n; while(l <= h) { m = (l+h) / 2; if(arr(m) >= A) { upmin(leftmostBig, m); h = m - 1; } else { l = m + 1; } } } void make_answer(vll& inds) { vi res(k); rep(i, 0, k) res[i] = inds[i]+1; answer(res); } bool is_good(ll v) { return A <= v && v <= 2*A; } ll sum(vll& inds) { ll tot = 0; for(const auto& ind : inds) { tot += arr(ind); } return tot; } bool use_big() { if(leftmostBig < k) return false; if(leftmostBig == n) return false; vll inds; rep(i, 0, k-(ll)1) inds.push_back(i); inds.push_back(leftmostBig); if(is_good(sum(inds))) { make_answer(inds); return true; } return false; } bool all_small() { vll inds(k); rep(i, 0, k) inds[i] = i; if(is_good(sum(inds))) { make_answer(inds); return true; } if(sum(inds) > 2*A) return false; for(ll i = k - 1, j = 0; i >= 0; i--, j++) { inds[i] = leftmostBig - 1 - j; if(is_good(sum(inds))) { make_answer(inds); return true; } } return false; } void solve(int N, int K, long long Aq, int S) { //pr("solving"); n = N, k = K, A = Aq, s = S; a.resize(n, -1); find_leftmost_big(); //wpr(leftmostBig); if(use_big()) return; if(all_small()) return; impossible(); } /* 6 3 5 1000 1 2 8 9 10 11 */
#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...