| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 946071 | Pikachu | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(long long n, long long k, long long A, long long s)
{
vector<long long> a(n + 2, -1);
long long sum = 0;
for (long long i = 1; i <= k; i++) {
a[i] = skim(i);
sum += a[i];
}
if (sum > 2ll * A) impossible();
if (sum >= A) {
vector<int> ans;
for (long long i = 1; i <= k; i++) ans.push_back(i);
answer(ans);
}
long long l = 1, r = n, oe = n + 1;
while (l <= r) {
long long mid = (l + r) >> 1;
if (skim(mid) >= A) {
oe = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (oe != n + 1) {
if (sum - a[k] + a[oe] <= 2ll * A) {
vector<int> ans;
for (long long i = 1; i < k; i++) {
ans.push_back(i);
}
ans.push_back(oe);
answer(ans);
}
}
oe--;
long long dak = 0;
for (long long i = oe; i > oe - k; i--) {
a[i] = skim(i);
dak += a[i];
}
if (dak < A) impossible();
for (long long i = oe; i > oe - k; i--) {
vector<int> ans;
long long lef = k - (oe - i + 1);
long long sum = 0;
for (long long j = 1; j <= lef; j++) {
ans.push_back(j);
sum += a[j];
}
for (long long j = i; j <= oe; j++) {
ans.push_back(j);
sum += a[j];
}
if (A <= sum && sum <= 2ll * A) {
answer(ans);
}
}
impossible();
}