| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1224377 | KALARRY | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
//chockolateman
#include<bits/stdc++.h>
#include"books.h"
using namespace std;
int a[100005];
void solve(int N,int K,int A,int S)
{
int l = 1;
int r = N;
for(int i = 1 ; i <= min(N,10) ; i++)
a[i] = skim(i);
int sum_l = 0;
vector<int> ret;
for(int i = 1 ; i <= K ; i++)
sum_l += a[i];
if(sum_l > 2*A)
impossible();
else if(A <= sum_l && sum_l <= 2*A)
{
for(int i = 1 ; i <= K ; i++)
ret.push_back(i);
}
else
{
while(l < r - 1) //searching for first val >= A
{
int mid = (l + r + 1)/2;
if(!a[mid])
a[mid] = skim(mid);
if(a[mid] < A)
l = mid + 1;
else if(a[mid])
r = mid;
}
if(l==r-1)
{
if(!a[l])
a[l] = skim(l);
if(a[l] >= A)
r = l;
}
if(!a[r])
a[r] = skim(r);
int sum_temp = sum_l - a[K] + a[r];
if(sum_temp > 2*A)
{
r--;
int sum_r = 0;
printf("IN\n");
for(int i = r ; i >= max(r - K + 1,1) ; i--)
{
if(!a[i])
a[i] = skim(i);
sum_r += a[i];
}
if(sum_r < A)
impossible();
int cur_sum = sum_l;
int pos = 0;
for(int j = 1 ; j <= K ; j++)
{
sum_l += a[r - j + 1] - a[K - j + 1];
if(A <= sum_l && sum_l <= 2*A)
{
pos = j;
}
}
for(int i = 1 ; i <= K - pos ; i++)
ret.push_back(i);
for(int i = r - pos + 1 ; i <= r ; i++)
ret.push_back(i);
}
else
{
for(int i = 1 ; i < K ; i++)
ret.push_back(i);
ret.push_back(r);
}
}
answer(ret);
}