Submission #417082

#TimeUsernameProblemLanguageResultExecution timeMemory
417082keko37A Difficult(y) Choice (BOI21_books)C++14
0 / 100
1 ms200 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; // // --- 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. // typedef long long llint; const int MAXN = 100005; int n; int val[MAXN], bio[MAXN]; vector <int> get_bio () { vector <int> res; for (int i = 1; i <= n; i++) { if (bio[i]) res.push_back(i); } return res; } void solve (int N, int k, llint a, int s) { n = N; llint sum = 0; for (int i = 1; i <= k - 1; i++) { val[i] = skim(i); sum += val[i]; } if (sum >= a) { sum += skim(k); if (a <= sum && sum <= 2 * a) { vector <int> tmp; for (int i = 1; i <= k; i++) { tmp.push_back(i); } answer(tmp); } else { impossible(); } return; } int lo = k, hi = n + 1; while (lo < hi) { int mid = (lo + hi) / 2; val[mid] = skim(mid); if (val[mid] > a) { hi = mid; } else { lo = mid + 1; } } if (lo != n + 1 && sum + val[lo] <= 2 * a) { vector <int> tmp; for (int i = 1; i <= k - 1; i++) tmp.push_back(i); tmp.push_back(lo); answer(tmp); return; } if (lo == k) return; val[lo - 1] = skim(lo - 1); sum += val[lo - 1]; for (int i = 1; i <= k - 1; i++) bio[i] = 1; bio[lo - 1] = 1; if (a <= sum && sum <= 2 * a) { answer(get_bio()); return; } for (int i = 1; i <= k - 1; i++) { sum -= val[k - i]; bio[k - i] = 0; val[lo - 1 - i] = skim(lo - 1 - i); sum += val[lo - 1 - i]; bio[lo - 1 - i] = 1; if (a <= sum && sum <= 2 * a) { answer(get_bio()); 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...