Submission #419914

#	Time	Username	Problem	Language	Result	Execution time	Memory
419914		blue	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	72 ms	1108 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

/*
Binary search for first book i >= A.
Answer is either this book + first K-1 books, or a subset of (first K books + last K books before i)
*/

       //books, choice size, limit,  skim limit
void solve(int N, int K, long long A, int S)
{
    vector<long long> difficulty(N+1, -1);

    int bigbook_low = 1, bigbook_high = N;
    while(bigbook_low != bigbook_high)
    {
        int m = (bigbook_low + bigbook_high)/2;
        if(skim(m) < A) bigbook_low = m+1;
        else bigbook_high = m;
    }

    int bigbook = bigbook_low;

    set<int> potential_books_set;
    for(int i = 1; i <= K; i++)
        potential_books_set.insert(i);

    for(int i = max(1, bigbook - K); i <= bigbook; i++)
        potential_books_set.insert(i);

    vector<int> potential_books;
    for(int b: potential_books_set)
        potential_books.push_back(b);

    int X = potential_books.size();

    for(int b: potential_books)
        difficulty[b] = skim(b);

    for(int mask = 0; mask < (1 << X); mask++)
    {
        int ct1 = 0;
        for(int i = 0; i < X; i++)
            if(mask & (1 << i))
                ct1++;

        if(ct1 != K) continue;

        long long sm = 0;
        for(int i = 0; i < X; i++)
            if(mask & (1 << i))
                sm += difficulty[potential_books[i]];

        if(A <= sm && sm <= 2*A)
        {
            vector<int> res;
            for(int i = 0; i < X; i++)
                if(mask & (1 << i))
                    res.push_back(potential_books[i]);

            answer(res);
        }
    }

    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