Submission #722542

#TimeUsernameProblemLanguageResultExecution timeMemory
722542lovrotA Difficult(y) Choice (BOI21_books)C++17
0 / 100
0 ms208 KiB
#include <bits/stdc++.h> #include "books.h" #define X first #define Y second #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; // g++ books_sample.cpp sample_grader.cpp void solve(int n, int k, long long a, int s) { impossible(); int cnt = 0; vector<int> ans; vector<pair<int, ll>> v1, v2; int lo = 1, hi = n + 1; while(hi - lo > 1) { int mi = (lo + hi) / 2; cnt++; if(skim(mi) >= a) hi = mi; else lo = mi; } ll sum = skim(hi); cnt++; if(hi != n + 1 && sum <= 2 * a) { ans.pb(hi); for(int i = 1; i < k; i++) { ll res = skim(i); cnt++; sum += res; ans.pb(i); v1.pb({i,res}); } assert(cnt <= s); if(sum <= 2 * a) { answer(ans); return; } } sum = 0; ans.clear(); v1.pb({k, skim(k)}); cnt++; for(int i = hi - 1; i && k; i--, k--) { v2.pb({i, skim(i)}); cnt++; sum += v2.back().Y; ans.pb(i); } assert(cnt <= s); if(sum >= a && sum <= 2 * a) { answer(ans); return; } for(pair<int, ll> p : v1) { sum -= v2.back().Y; sum += p.Y; ans.pop_back(); ans.pb(p.X); if(sum >= a && sum <= 2 * a) { answer(ans); return; } } impossible(); }
#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...