| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1334381 | yc11 | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int N, int K, long long A, int S) {
long long a = 1;
long long b = N;
vector<long long> n1;
vector<int> pre;
n1.assign(N,-1);
while (a<b){
long long x = (a+b)/2;
n1[x-1] = skim(x);
if (n1[x-1]>=A) b = x;
else a = x+1;
}
long long ans;
if (n1[b-1]==-1) n1[b-1] = skim(b);
ans = n1[b-1];
for (int i = 0;i<K-1;i++){
if (n1[i]==-1) n1[i] = skim(i+1);
ans = ans+n1[i];
}
if (ans=<2*A and ans>=A){
vector<int> a;
a.push_back(b);
for (int i = 0;i<K-1;i++) a.push_back(i+1);
answer(a);
return;
}
if (ans>2*A){
int b1 = b;
ans = ans-n1[b-1];
if (n1[K-1]==-1) n1[K-1] = skim(K);
ans = ans+n1[K-1];
int c = 0;
b--;
while (ans<A){
if (c+K>=b+1) break;
if (n1[b]==-1) n1[b]=skim(b+1);
ans = ans-n1[c]+n1[b];
c++;
b--;
if (c==K) break;
}
if (ans>=A and 2*A>=ans){
vector<int> a;
for (int i = c;i<K;i++) a.push_back(i+1);
for (int i = b+1;i<b1;i++) a.push_back(i+1);
answer(a);
return;
}
}
else{
int b1 = b;
int c = 0;
b--;
b--;
while (ans<A){
if (c+K>=b+1) break;
if (n1[b]==-1) n1[b]=skim(b+1);
ans = ans-n1[c]+n1[b];
c++;
b--;
if (c==K) break;
}
if (ans>=A and 2*A>=ans){
vector<int> a;
for (int i = c;i<K-1;i++) a.push_back(i+1);
for (int i = b+1;i<b1;i++) a.push_back(i+1);
answer(a);
return;
}
}
impossible();
}