| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1188491 | DanielPr8 | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include"books.h"
using namespace std;
using ll = __int128_t;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vll passs;
ll k, a;
ll ski(ll a){
if(passs[a]==-1)return passs[a]=skim(a);
return passs[a];
}
void sto(){
while(true){
cout << "";
}
}
void answr(vector<int> id){
if(id.size()!=k)sto();
ll ans=0;
for(ll i:id)ans+=ski(i);
if(ans>a*2)sto();
if(ans<a)sto();
answer(id);
}
void solve(int n, int k1, long long a1, int Q) {
k=k1;a=a1;
ll s = 1, e = n, m;
passs = vll(n+1,-1);
while(s<e){
m = (s+e+1)/2;
ll t = ski(m);
if(t>a)e=m-1;
else s=m;
}
vll v1(k), v2;
vector<int> id;
ll v3=-1;
for(ll i = 0; i < k; ++i){v1[i] = ski(i+1);}
for(ll i = max<ll>(1, s-k+1); i <= s; ++i){v2.pb(ski(i));id.pb(i);}
if(s<n)v3=ski(s+1);
ll p1=0, p2=0;
for(ll i:v1)p1+=i;
for(ll i:v2)p2+=i;
if(p1>2*a)impossible();
else if(k<=s){
if(p2>=a){
for(ll i = 0; i < k; ++i){
if(p2<=2*a)break;
id[i]=i+1;
p2 += v1[i]-v2[i];
}
answer(id);
}
else if(s<n){
iota(all(id),1);
id.back()=s+1;
if(p1-v1.back()+v3<=a*2)answer(id);
else impossible();
}
else impossible();
}
else{
id=vll(k);
iota(all(id),1);
if(p1>=a)answr(id);
else impossible();
}
}