| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1354172 | lizi14 | 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 fi=skim(1);
long long bol=skim(N);
if(fi>2*A){
//cout<<"II"<<endl;
impossible();
return;
}
long long l=1,r=N;
long long ans=-1;
long long gvanca[N+1];
long long x[N+1];
fill(x,x+N+1,0);
x[1]=fi;
x[N]=bol;
//if(bol<=A){
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;
}
}
//}
if(ans==-1){
ans=N+1;
x[0]=fi;
x[N]=bol;
for(int i=2; i<=K; i++){
if(x[i]!=0)continue;
long long a=skim(i);
x[i]=a;
}
for(int i=N-1; i>=N-K+1; i--){
if(x[i]!=0)continue;
//cout<<i<<" ";
//cout<<i<<" "<<N-K<<endl;
x[i]=skim(i);
//cout << 1;
}
//cout<<"BATII!"<<endl;
long long sum=0;
for(int i=1; i<=K; i++){
sum+=x[i];
}
//cout<<sum<<endl;
if(sum>2*A){
//cout<<"YY"<<endl;
impossible();
return;
}
if(sum>=A && sum<=2*A){
vector<long long>anss;
anss.clear();
for(int i=1; i<=K; i++){
anss.push_back(i);
}
//cout<<"1"<<endl;
answer(anss);
return;
}
vector<long long> g;
g.clear();
for(int i=1; i<=K; i++){
//sum-=x[i];
if(x[ans-K-i]==0){
x[ans-K-i]=skim(ans-K-i);
}
sum+=abs(x[i]-x[ans-K-i]);
g.push_back(ans-K-i);
if(sum>=A && sum<=2*A){
vector<int>ja=g;
for(int j=i+1; j<=K; j++){
ja.push_back(j);
}
//cout<<2<<endl;
answer(ja);
return;
}
//cout<<sum<<endl;
}
//cout<<"$"<<endl;
impossible();
return;
}
else{
// int x[N+1];
// fill(x,x+N+1,0);
x[0]=fi;
x[N]=bol;
for(int i=2; i<=K; i++){
if(x[i]!=0)continue;
long long a=skim(i);
x[i]=a;
}
for(int i=ans-1; i>=ans-K+1; i--){
if(x[i]!=0)continue;
long long a=skim(i);
x[i]=a;
}
long long sum=0;
for(int i=1; i<=K; i++){
sum+=x[i];
}
if(sum>2*A){
//cout<<"IO"<<endl;
impossible();
return;
}
if(sum>=A && sum<=2*A){
vector<long long>anss;
for(int i=1; i<=K; i++){
anss.push_back(i);
}
//cout<<3<<endl;
answer(anss);
return;
}
vector<long long>g;
for(int i=1; i<=K; i++){
if(x[ans-K-i]==0){
x[ans-K-i]=skim(ans-K-i);
}
sum+=abs(x[i]-x[ans-K-i]);
g.push_back(ans-K-i);
if(sum>=A && sum<=2*A){
vector<int>ja=g;
for(int j=i+1; j<=K; j++){
ja.push_back(j);
}
//cout<<4<<endl;
answer(ja);
return;
}
}
long long gag=0;
vector<int>o;
x[ans]=skim(ans);
gag+=x[ans];
//cout<<ans<<endl;
//cout<<x[ans]<<" ";
o.push_back(ans);
for(int i=1; i<=K-1; i++){
if(x[i]!=0)continue;
else x[i]=skim(i);
gag+=x[i];
o.push_back(i);
}
if(gag>=A && gag<=2*A){
//cout<<5<<endl;
answer(o);
return;
}
//cout<<gag<<endl;
//cout<<"?"<<endl;
impossible();
return;
}
}