Submission #1224361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224361		sokratisi	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	1176 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> books;
vector<int> ans;

long long get_books(int a) {
    if (books[a]) return books[a];
    return books[a] = skim(a);
}

void solve(int n, int k, long long a, int s) { // check kamia mlkia pou vazeis polles fores to idio
    // TODO implement this function
    books.resize(n+1);
    long long sm = 0;
    for (int i = 1; i <= k; i++) sm += get_books(i);

    if (sm > 2*a) impossible();
    if (sm >= a) {
        for (int i = 1; i <= k; i++) ans.push_back(i);
        answer(ans);
    }
    sm = 0;
    
    int l = 1, r = n, fp = n+1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (get_books(m) < a) {
            l = m+1;
        }
        else {
            fp = m;
            r = m-1;
        }
    }
    if (fp != n+1) {
        if (fp <= k) impossible();
        sm = get_books(fp);
        for (int i = 1; i < k; i++) {
            sm += get_books(i);
        }
        if (sm <= 2*a) {
            for (int i = 1; i < k; i++) ans.push_back(i);
            ans.push_back(fp);
            answer(ans);
        }
        sm = 0;
    }
    // we have fp > k
    for (int i = fp - k; i < fp; i++) sm += get_books(i);
    if (sm < a) impossible();
    for (int i = fp-k; i < fp; i++) ans.push_back(i);
    int ind = 1;
    while (sm > 2*a) {
        ans[ind] = ind;
        sm += get_books(ind) - get_books(ind - 1 + fp - k);
        ind++;
    }
    answer(ans);
}

• 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