| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1368632 | 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"
#define pb push_back
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];
ll 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];
ll liam_with_blond_hair_was_better=0;
if(ans!=-1){
liam_with_blond_hair_was_better=ans;
sss+=x[ans];
vector<int>as;
if(sss>=A && sss<=2*A){
for(int i=1; i<=K-1; i++){
as.push_back(i);
}
as.push_back(ans);
answer(as);
return;
}
}
else{
liam_with_blond_hair_was_better=N+1;
}
vector<pair<int,int>>vec(K+1);
int ii=1;
for(int i=liam_with_blond_hair_was_better-1; liam_with_blond_hair_was_better-1-K; i--){
if(x[i]==0){
x[i]=skim(i);
}
vec[ii].f=x[i];
vec[ii].ss=i;
ii++;
}
vector<int>liam;
for(int i=1; i<=K; i++){
sum+=vec[i].first-x[i];
// vec[i].first=vecc[i].first;
// vec[i].second=vecc[i].second;
if(sum>=A and sum<=2*A){
for(int i=1; i<=K; i++){
liam.push_back(vec[i].second);
}
answer(liam);
return;
}
}
impossible();
}