제출 #1283468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283468		weebyeah	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	408 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

#define Ilveyuki ios::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
//
// --- Sample implementation for the task books ---
//
// To compile trs program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int K, ll A, int S)
{
    map<int, ll> m;

    int l = 1, r = N + 1;
    while (l < r)
    {
        int mid = l + (r - l) / 2;

        if (!m[mid])
            m[mid] = skim(mid);

        if (m[mid] > A)
            r = mid;
        else
            l = mid + 1;
    }

    int t = l;


    vector<ll> lp(K + 1);
    for (int i = 1; i <= K; i++)
    {
        if (!m[i])
            m[i] = skim(i);

        lp[i] = lp[i - 1] + m[i];
    }

    if (t <= N)
    {
        if (!m[t])
            m[t] = skim(t);

        ll tot = lp[K - 1] + m[t];
        if (A <= tot && tot <= 2 * A)
        {
            vector<int> res;
            for (int i = 1; i <= K - 1; i++)
            {
                res.push_back(i);
            }

            res.push_back(t);
            answer(res);

            return;
        }
    }

    if (t - 1 < K)
    {
        impossible();
        return;
    }

    vector<ll> rs(K + 1);
    for (int i = 1; i <= K; i++)
    {
        if (!m[t - i])
            m[t - i] = skim(t - i);

        rs[i] = rs[i - 1] + m[t - i];
    }

    for (int i = 0; i <= K; i++)
    {
        ll tot = lp[K - i] + rs[i];
        if (A <= tot && tot <= 2 * A)
        {
            vector<int> res;
            for (int j = 1; j <= K - i; j++)
            {
                res.push_back(j);
            }

            for (int j = t - i; j <= t - 1; j++)
            {
                res.push_back(j);
            }

            answer(res);
            return;
        }
    }

    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