| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1288916 | BigBadBully | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "books.h"
#define int long long
#define pii pair<int,int>
using namespace std;
void solve(signed n,signed k,int a,signed s)
{
vector<int> v(n,-1);
auto f = [&](int idx)
{
if(v[idx] < 0)
v[idx] = skim(idx+1);
return v[idx];
};
auto check = [&](int i)
{
int prev = f(i);
int sum = prev;
for (int j = i+1;j-i < k; j++)
{
prev = max(prev+1,v[j]);
sum+=prev;
}
return sum < a;
};
int l = 0,r = n-k;
while(r-l)
{
int mid = l+r>>1;
if(check(mid))
l = mid+1;
else
r = mid;
}
auto gt = [&](int i)
{
int sum = 0;
for (int j = i; j < i+k; j++){
if(v[j]<0)return 4*a;
sum+=v[j];
}
return sum;
};
auto ende = [&](int idx)
{
if(gt(idx) >= a && gt(idx) <= 2*a)
{
vector<int> ans;
for (int h = idx;h < idx+k;h++)ans.push_back(h+1);
answer(ans);
return true;
}
return false;
};
{
int sum = f(l);
int i = l+1;
for (;i-l < k && f(i) < a; sum+=f(i),i++);
r = i;
if(i < k-1)
{
impossible();
return;
}
}
if (ende(l))return;
int i = l-1;
for (; i >= 0 && f(i) && gt(i) >= a; i--);
for (int j = i; gt(j) <= 2*a;j++)
if(ende(j))return;
int sm = 0;
for (int i = 0 ; i < k-1; i++)
sm+=f(i);
if(a <= sm+f(r) && sm+f(r) <= 2*a)
{
vector<int> ans;
for (int i = 0; i < k-1; i++)ans.push_back(i+1);
ans.push_back(r+1);
answer(ans);
}
else
impossible();
}