Submission #953817

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

//
// --- Sample implementation for the task books ---
//
// To compile this 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.
//

vector<long long> vals;

long long query(int i) {
    if (vals[i] == -1) {
        vals[i] = skim(i+1);
    }

    return vals[i];
}

void solve(int N, int K, long long A, int S) {
    vals.assign(N, -1);

    int l = 0, r = N - K;
    int cand = -1;

    while (l <= r) {
        int m;
        if (r-l >= 100) {
            m = l + (r-l)/4;
        }

        else {
            m = l + (r-l)/2;
        }

        long long tmpSum = 0;
        for (int i=K-1;i>=0;i--) {
            if (tmpSum + (i+1)*query(m+i) < A) {
                tmpSum = -10;
                break;
            }

            tmpSum += query(i+m);

            if (tmpSum + i > 2LL*A) {
                tmpSum = 2LL*A + 1LL;
                break;
            }
        }

        if (A <= tmpSum && tmpSum <= 2LL*A) {
            vector<int> idx;
            for (int i=0;i<K;i++)idx.push_back(i+m+1);
            answer(idx);
            return;
        }

        else if (tmpSum < A) {
            l = m+1;
        }

        else {
            r = m-1;
            cand = m;
        }
    }

    long long possum = query(cand + K - 1);
    for (int i=0;i<K-1;i++) {
        possum += query(i);
    }

    if (A <= possum && possum <= 2*A) {
        vector<int> idx;
        for (int i=0;i<K-1;i++) idx.push_back(i+1);
        idx.push_back(cand+K);
        answer(idx);
        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