| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1334324 | zhehan | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "books.h"
#define int long long
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.
//
void solve(int N, int K, long long A, int S) {
// TODO implement this function
int l = 1, r = N, m, o;
while (l < r) {
m = (l + r) / 2;
o = skim(m);
if (o == A) {
l = m;
break;
}
if (o < A) {
l = m + 1;
} else {
r = m;
}
}
if (l < K) {
impossible();
}
vector<int> selected_books(K, 0);
vector<int> ind(K, 0);
ind[K - 1] = l;
selected_books[K - 1] = skim(l);
int sum = selected_books[K - 1];
bool offset = false;
if (selected_books[K - 1] < A) {
offset = true;
}
for (int i = 1; i < K; ++i) {
selected_books[i - 1] = skim(i);
ind[i - 1] = i;
sum += selected_books[i - 1];
}
if (sum < 2 * A && sum > A) {
answer(ind);
}
if (l == K) {
impossible();
}
selected_books[K - 1] = skim(K);
sum = sum - o + selected_books[K - 1];
ind[K - 1] = K;
if (sum < 2 * A && sum > A) {
answer(ind);
}
for (int i = 0; i < K; ++i) {
if (l - K + i <= K) {
impossible();
}
int j = l - K + i;
if (offset) {
++j;
}
int curr = skim(j);
sum = sum - selected_books[i] + curr;
selected_books[i] = curr;
ind[i] = j;
if (sum < 2 * A && sum > A) {
answer(ind);
}
}
impossible();
}