Submission #1188635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188635		peteza	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	0 ms	428 KiB

books

#include <bits/stdc++.h>

#include "books.h"
using namespace std;
using ll = long long;

//
// --- 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.
//

ll val[100005];

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    ll csum = 0;
    for(int i=1;i<=K;i++) {
        val[i] = skim(i);
        csum += val[i];
    }
    if(csum > 2*A) {impossible(); return;}
    if(csum >= A) {
        vector<int> vecss(K);
        for(int i=0;i<K;i++) vecss[i] = i+1;
        answer(vecss);
        return;
    }
    csum -= val[K];
    int l = K, r = N;
    while(l <= r) {
        int mid = (l+r) >> 1;
        val[mid] = skim(mid);
        if(csum + val[mid] < A) l = mid+1;
        else r=mid-1;
    }
    l = r;
    //wttttttf
    //123,...,K-1, l is surely less than A
    if(l != N) {
        val[l+1] = skim(l+1);
        if(csum + val[l+1] >= A && csum + val[l+1] <= 2*A) {
            vector<int> vecss(K);
            for(int i=0;i<K-1;i++) vecss[i] = i+1;
            vecss[K-1] = l+1;
            answer(vecss);
            return;
        }
    }
    //lolllllllllllllllllllllllllllllllllllllllll
    for(int i=2;i<=K;i++) {
        csum = 0;
        vector<int> frfr;
        for(int j=1;j<=K-i;j++) {
            csum += val[j];
            frfr.push_back(j);
        }
        val[l-i+1] = skim(l-i+1);
        for(int j=l-i+1;j<=l;j++) {
            csum += val[j];
            frfr.push_back(j);
        }
        if(csum >= A && csum <= 2*A) {
            answer(frfr);
            return;
        }
    }
    impossible();
    /*
    if (skim(2) == 42) {
        impossible();
    } else {
        answer({1, 3});
    }*/
}

//g++ books.cpp grader.cpp -o books
/*
15 3 42 40
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/

• 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