# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
506289 | Elegia | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cmath>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#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.
//
long long arr[25];
void solve(int N, int K, long long A, int S) {
int low = 1, high = N + 1;
long long C = (A + K - 1) / K, temp;
while (low < high) {
int mid = (low + high) / 2;
if ((temp = skim(mid)) >= C) {
high = mid;
arr[K] = temp;
}
else low = mid + 1;
}
if (low > N) return impossible();
for (int i = 1; i < K; ++i)
arr[K - i] = i < low ? skim(low - i) : (A * 2 + 1);
for (int i = 1; i < K; ++i)
arr[K + i] = i + low <= N ? skim(i + low) : (A * 2 + 1);
for (int i = 1; i <= K; ++i) {
long long sum = accumulate(arr + i, arr + i + K, 0LL);
if (sum >= A && sum <= A * 2) {
vector<int> ans(K);
iota(ans.begin(), ans.end(), low - K + i);
return answer(ans);
}
}
long long sum = 0, temp;
for (int i = 1; i != K; ++i) sum += skim(i);
low = K; high = N + 1;
while (low < high) {
int mid = (low + high) / 2;
if ((temp = skim(mid)) >= A - sum) {
if (temp + sum <= A * 2) {
vector<int> ans(K);
iota(ans.begin(), ans.end(), 1);
ans[K - 1] = mid;
return answer(ans);
}
high = mid;
}
else low = mid + 1;
}
return impossible();
}