Submission #1288917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288917		BigBadBully	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	2 ms	1168 KiB

books

#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<signed> 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<signed> ans;
        for (int i = 0; i < k-1; i++)ans.push_back(i+1);
        ans.push_back(r+1);
        answer(ans);
    }
    else
        impossible();
    
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20