Submission #598095

#	Time	Username	Problem	Language	Result	Execution time	Memory
598095		boris_mihov	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	1 ms	336 KiB

books

#include <iostream>
#include "books.h"

typedef long long llong;
const int MAXN = 100000 + 10;
llong a[MAXN];

llong getValue(int pos)
{
    if (a[pos] != 0) return a[pos];
    return a[pos] = skim(pos);
}

void solve(int n, int k, long long A, int s) 
{
    int l = 0, r = n+1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        getValue(mid);
        if (a[mid] <= A) l = mid;
        else r = mid;
    }

    if (r < k)
    {
        impossible();
        return;
    }

    if (r <= n) getValue(r);
    llong sum = a[r];
    std::vector < int > ans;
    for (int i = 1 ; i <= k-1 && k <= r ; ++i)
    {
        ans.push_back(i); getValue(i);
        sum += a[i];
    }

    if (r <= n && A <= sum && sum <= 2*A)
    {
        ans.push_back(r);
        answer(ans);
        return;
    }

    sum = 0;
    ans.clear();
    for (int i = 1 ; i <= k ; ++i)
    {
        getValue(i);
        sum += a[i];
        ans.push_back(i);
    }

    if (2*k <= r-1)
    {
        int cnt = 1;
        for (int i = r-1 ; i >= r-k-1 ; --i)
        {
            if (A <= sum && sum <= 2*A)
            {
                answer(ans);
                return;
            }

            if (i == r-k-1) break;
            sum -= a[cnt++]; getValue(i);
            sum += a[i];
            ans.erase(ans.begin());
            ans.push_back(i);
        }
    } else
    {
        for (int i = k+1 ; i <= r ; ++i)
        {
            if (A <= sum && sum <= 2*A)
            {
                answer(ans);
                return;
            }

            if (i > n) break;
            sum -= a[i-k]; getValue(i);
            sum += a[i];
            ans.erase(ans.begin());
            ans.push_back(i);
        }
    }

    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