Submission #769432

#	Time	Username	Problem	Language	Result	Execution time	Memory
769432		raysh07	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	37 ms	1180 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 useless) {
    // // TODO implement this function
    // if (skim(2) == 42) {
    //     impossible();
    // } else {
    //     answer({1, 3});
    // }
    
    vector <long long> b(n + 1, -1);
    long long sum = 0;
    for (int i = 1; i < k; i++) b[i] = skim(i), sum += b[i];
    
    int l = k, r = n + 1;
    while (l != r){
        int mid = (l + r)/2;
        
        long long x = skim(mid);
        if (sum + x >= a) r = mid;
        else l = mid + 1;
    }
    
    if (l <= n && sum + skim(l) <= 2 * a){
        vector <int> ans;
        for (int i = 1; i < k; i++) ans.push_back(i);
        ans.push_back(l);
        answer(ans);
        return;
    }
    
    l--;
    set <pair<long long, int>> st;
    for (int i = 1; i < k; i++) st.insert({b[i], i});
    
    for (int i = l; i > l - k; i--){
        if (i <= 0) continue;
        
        b[i] = skim(i);
        st.insert({b[i], i});
    }
    
    vector <pair<long long, int>> ok;
    for (auto x : st) ok.push_back(x);
    
    int sz = ok.size();
    for (int i = 0; i < (1 << sz); i++){
        int cnt = 0;
        long long sum1 = 0;
        
        for (int j = 0; j < sz; j++){
            if (i >> j & 1){
                cnt++;
                sum1 += ok[j].first;
            }
        }
        
        if (cnt != k) continue;
        
        if (sum1 >= a && sum1 <= 2 * a) {
            vector <int> ans;
            for (int j = 0; j < sz; j++){
                if (i >> j & 1) ans.push_back(ok[j].second);
            }
            
            answer(ans);
            return;
        }
    }
    
    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