Submission #418359

#	Time	Username	Problem	Language	Result	Execution time	Memory
418359		johutha	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	304 KiB

books

#include <vector>
#include <iostream>
#include <algorithm>
 
#include "books.h"

#define int long long
 
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(signed N, signed K, int A, signed S) {
    
    vector<int> lowest(K);
    int losum = 0;    
    for(int i = 0; i < K; i ++)
    {
        lowest[i] = skim(i + 1);
        losum += lowest[i];
    }
 
    vector<signed> ansvec(K);
    for(int i = 0; i < K; i ++) ansvec[i] = i + 1;
 
    if(losum > 2 * A) impossible();
    else if(losum >= A) answer(ansvec);
 
    int lo = 0, hi = N;
    while(lo + 1 < hi)
    {
        int m = (lo + hi) / 2;
        if(skim(m + 1) < A) lo = m;
        else hi = m;
    }
 
    if(hi < N && losum - lowest[K - 1] + skim(hi + 1) <= 2 * A)
    {
        ansvec[K - 1] = hi + 1;
        answer(ansvec);
        return;
    }
 
    hi --;
    if(hi < K) impossible();
 
    int j = 0;
    while(losum < A && hi > j && j < K)
    {
        losum += skim(hi + 1) - lowest[j];
        ansvec[j] = hi + 1;
        j ++;
        hi --;
    }
    if(losum < A) impossible();
    else answer(ansvec);
}

• 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