| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1368625 | lizi14 | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include"books.h"
void solve(int N, int K, long long A, int S){
long long fi=skim(1);
long long bol=skim(N);
if(fi>2*A){
impossible();
return;
}
long long l=1,r=N;
long long ans=-1;
long long gvanca[N+1];
int x[N+1];
fill(x,x+N+1,0);
x[1]=fi;
x[N]=bol;
while(l<=r){
long long m=(l+r)/2;
long long bati;
if(x[m]==0){
bati=skim(m);
x[m]=bati;
}
else bati=x[m];
if(bati>=A){
ans=m;
r=m-1;
}
else{
l=m+1;
}
}
ll sum=0;
for(int i=1; i<=K; i++){
if(x[i]==0){
int a=skim(i);
x[i]=a;
}
sum+=x[i];
}
if(sum>2*A){
impossible();
return;
}
if(sum>=A && sum<=2*A){
vector<int>bati;
for(int i=1; i<=k; i++){
bati.pb(i);
}
answer(bati);
return;
}
ll sss=sum-x[k];
int liam_with_blond_hair_was_better=0;
if(ans!=-1){
liam_with_blond_hair_was_better=x[ans];
vector<int>as;
if(sss+ans>=A && sss+ans<=2*A){
for(int i=1; i<=K-1; i++){
as.push_back(i);
}
as.push_back(liam_with_blond_hair_was_better);
answer(as);
return;
}
}
else{
liam_with_blond_hair_was_better=N+1;
}
for(int i=liam_with_blond_hair_was_better-1; i>=liam_with_blond_hair_was_better-K; i--){
if(x[i]==0){
x[i]=skim(i);
}
}
vector<int>cacmiycmh;
for(int i=1; i<=K; i++){
sum+=x[i+k]-x[i];
x[i]=x[i+k];
if(sum>=A and sum<=2*A){
for(int i=1; i<=K; i++){
cacmiycmh.pb(i);
}
answer(cacmiycmh);
return;
}
}
impossible();
}