Submission #1016306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016306		MohamedFaresNebili	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.
//

void solve(int N, int K, long long A, int S) {
    long long sum = 0;
    vector<long long> arr(N + 1, -1);
    for(int l = 1; l < K; l++) {
        arr[l] = skim(l);
        sum += arr[l]; 
    }
    int lo = K, hi = N, ind = -1;
    while(lo <= hi) {
        int md = (lo + hi) / 2;
        if(arr[md] == -1)
            arr[md] = skim(md);
        if(arr[md] > A) ind = md, hi = md - 1;
        else lo = md + 1; 
    }

    if(ind >= K && sum + arr[ind] >= A && sum + arr[ind] <= 2LL * A) {
        vector<int> res;
        for(int l = 1; l < K; l++) res.push_back(l);
        res.push_back(ind);
        answer(res); return;
    }

    if(arr[K] == -1) arr[K] = skim(K);
    sum += arr[K];
    if(sum >= A && sum <= 2LL * A) {
        vector<int> res;
        for(int l = 1; l <= K; l++) res.push_back(l);
        answer(res); return;
    }

    if(ind == -1 || ind < 2 * K) ind = N + 1;

    lo = 1, hi = ind - 1;
    while(lo <= K) {
        sum -= arr[lo];
        if(arr[hi] == -1) arr[hi] = skim(hi); 
        sum += arr[hi];
        if(sum >= A && sum <= 2LL * A) {
            vector<int> res;
            for(int l = lo + 1; l <= K; l++)
                res.push_back(l);
            for(int l = hi; l < ind; l++)
                res.push_back(l);
            answer(res); return;
        }
        lo++, hi--;
    }

    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