| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286709 | user736482 | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
void solve(int N,int K,ll a,int S){
ll n=N;
ll k=K;
ll s=S;
vi v;
ll b=0;
for(ll i=1;i<k;i++){
v.pb(skim(i));
b+=v.back();
}
ll pocz=k;
ll kon=n+1;
ll x,y=INFL;
while(pocz!=kon){
ll md=(pocz+kon)/2;
x=skim(md);
if(b+x<a)pocz=md+1;
else {kon=md;y=x;}
}
if(b+y<=2*a){
vector<int>ans;
for(ll i=1;i<k;i++)ans.pb(i);
ans.pb(pocz);
answer(ans);return;
}
x=pocz-1;
if(x<k){
impossible();return;
}
vector<int>ans;
v.pb(0);
for(ll i=1;i<=k;i++){
ans.pb(x);
b+=skim(x);
b-=v[v.size()-i];
x--;
if(b>=a){
for(ll j=1;j<=k-i;j++)ans.pb(j);
answer(ans);
}
}
impossible();
}
