Submission #401974

#	Time	Username	Problem	Language	Result	Execution time	Memory
401974		blue	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	968 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>
using namespace std;
 
long long n;
long long k;
long long a;
 
vector<long long> diff(100001);
 
vector<int> res;
long long curr_sum;
 
int L, R;
 
void res_search(long long l, long long books)
{
    // cerr << "rs " << l << ' ' << books << '\n';
 
 
    res.push_back(l);
    curr_sum += diff[l];
 
    if(books-1 == 0)
    {
        if(a <= curr_sum && curr_sum <= 2*a)
            answer(res);
 
        return;
    }
 
    for(long long r = l+1; r <= R; r++)
        res_search(r, books-1);
 
}
 
 
 
void binary_search(long long l, long long r)
{
    // cerr << "bs " << l << ' ' << r << '\n';
    if(l == r)
    {
        L = max(1LL, l-k);
        R = min(n, r+k);
        for(long long i = L; i <= R; i++)
            diff[i] = skim(i);
 
        res_search(L, k);
        impossible();
    }
    else
    {
        long long m = (l+r)/2 + 1;
        if(k*skim(m) <= a*2)
            return binary_search(m, r);
        else
            return binary_search(l, m-1);
    }
}
 
 
       //books, choice size, limit,  skim limit
void solve(int N, int K, long long A, int S)
{
    n = N;
    k = K;
    a = A;
 
    binary_search(1LL, n);
}

• 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