Submission #554608

#	Time	Username	Problem	Language	Result	Execution time	Memory
554608		yoavL	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	1064 KiB

books

#include <bits/stdc++.h>

#include "books.h"

#define pr(x) cout << x << endl
#define wpr(x) cout << #x << ": " << x << endl
#define rep(i, s, e) for(ll i = s; i < e ; i++)
#define upmin(a, b) (a) = min((ll)a, (ll)b)


using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;


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

vll a;
ll n, k, A, s;
ll leftmostBig;
ll arr(ll i)
{
    if(a[i] == -1) a[i] = skim(i+1);
    return a[i];
}

// Finds the left-most index whose value is at least A
void find_leftmost_big()
{
    ll l = 0, h = n-1, m;
    leftmostBig = n;
    while(l <= h) {
        m = (l+h) / 2;
        if(arr(m) >= A) {
            upmin(leftmostBig, m);
            h = m - 1;
        }
        else {
            l = m + 1;
        }
    }
}

void make_answer(vll& inds)
{
    vi res(k);
    rep(i, 0, k) res[i] = inds[i]+1;
    answer(res);
}

bool is_good(ll v)
{
    return A <= v && v <= 2*A;
}

ll sum(vll& inds)
{
    ll tot = 0;
    for(const auto& ind : inds) {
        tot += arr(ind);
    }
    return tot;
}

bool use_big()
{
    if(leftmostBig < k) return false;
    if(leftmostBig == n) return false;
    vll inds;
    rep(i, 0, k-(ll)1) inds.push_back(i);
    inds.push_back(leftmostBig);
    if(is_good(sum(inds))) {
        make_answer(inds);
        return true;
    }
    return false;
}


bool all_small()
{
    vll inds(k);
    rep(i, 0, k) inds[i] = i;
    if(is_good(sum(inds))) {
        make_answer(inds);
        return true;
    }
    if(sum(inds) > 2*A) return false;
    for(ll i = k - 1, j = 0; i >= 0; i--, j++) {
        inds[i] = leftmostBig - 1 - j;
        if(is_good(sum(inds))) {
            make_answer(inds);
            return true;
        }
    }
    return false;
}


void solve(int N, int K, long long Aq, int S) {
    //pr("solving");
    n = N, k = K, A = Aq, s = S;
    a.resize(n, -1);
    find_leftmost_big();
    //wpr(leftmostBig);
    if(use_big()) return;
    if(all_small()) return;
    impossible();
}



/*

6 3 5 1000

1 2 8 9 10 11

*/

• 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