Submission #418297

#	Time	Username	Problem	Language	Result	Execution time	Memory
418297		johutha	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	1 ms	200 KiB

books

#include <vector>
#include <iostream>
#include <algorithm>
 
#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) {
    
    vector<int> lowest(K);
    int losum = 0;    
    for(int i = 0; i < K; i ++)
    {
        lowest[i] = skim(i + 1);
        losum += lowest[i];
    }
 
    int lo = 0, hi = N - 1;
    while(lo + 1 < hi)
    {
        int m = (lo + hi) / 2;
        if(skim(m) < A) lo = m;
        else hi = m;
    }
    hi = max(hi, K - 1);
 
    vector<int> highest(K);
    int hisum = 0;
    for(int i = 0; i < K; i ++)
    {
        highest[i] = skim(hi - K + i + 2);
        hisum += highest[i];
    }
 
    if(hisum < A || losum > 2 * A) impossible();
    int cut = -1;
    while (losum < A)
    {
        cut ++;
        losum += highest[cut] - lowest[cut];
    }
    vector<int> ansvec(K);
    for(int i = 0; i < K; i ++)
    {
        if(i <= cut) ansvec[i] = hi - K + 2 + i;
        else ansvec[i] = i;
    } 
    for (auto &i : ansvec) i++;
 
    answer(ansvec);
 
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20