Submission #953745

#	Time	Username	Problem	Language	Result	Execution time	Memory
953745		asdasdqwer	A Difficult(y) Choice (BOI21_books)	C++14	60 / 100	135 ms	1992 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 subtask2(int N, int K, long long A, int S) {
    vector<long long> a(N);
    for (int i=0;i<N;i++) {
        a[i] = skim(i+1);
    }

    long long pref = 0;
    for (int i=0;i<K;i++) {
        pref += a[i];
    }

    if (pref > 2*A) {
        impossible();
        return;
    }

    auto it = lower_bound(a.begin(), a.end(), A);
    if (it != a.end()) {
        long long num = *it;
        for (int i=0;i<K-1;i++) num += a[i];
        if (num <= 2LL*A) {
            vector<int> idx;
            for (int i=0;i<K-1;i++) idx.push_back(i+1);
            idx.push_back(distance(a.begin(), it)+1);

            answer(idx);
            return;
        }
    }

    while (a.back() >= A)a.pop_back();

    for (int i=0;i<(int)a.size()-K+1;i++) {
        long long sum = 0;
        for (int j=0;j<K;j++) {
            sum += a[j+i];
        }

        if (A <= sum && sum <= 2LL*A) {
            vector<int> idx;
            for (int j=0;j<K;j++) {
                idx.push_back(i+j+1);
            }

            answer(idx);
            return;
        }
    }

    impossible();
}

vector<long long> vals;
int toge;
int qu;

long long query(int i) {
    if (vals[i] == -1) {
        qu++;
        assert(qu <= toge);

        vals[i] = skim(i+1);
    }

    return vals[i];
}

void solve(int N, int K, long long A, int S) {
    toge = S;
    qu=0;
    if (N <= S) {
        subtask2(N,K,A,S);
        return;
    }

    vals.assign(N, -1);

    // check first K values
    long long sum = 0;
    for (int i=0;i<K;i++) {
        sum += query(i);
    }

    if (sum > 2LL*A) {
        impossible();
        return;
    }

    if (sum >= A) {
        vector<int> idx;
        for (int i=0;i<K;i++) {
            idx.push_back(i+1);
        }
        answer(idx);
        return;
    }


    // binary search for the first value greater or equal to A
    int l = K, r = N-1;
    int ans = -1;
    long long valans = -1;
    while (l <= r) {
        int m = l + (r-l)/2;
        long long val = query(m);
        if (val == A) {
            ans = m;
            valans = A;
            break;
        }

        if (val < A) {
            l = m+1;
        }

        else {
            ans = m;
            valans = val;
            r = m-1;
        }
    }

    // check if prefix + a is fitting
    int last = N-1;
    if (ans != -1) {
        long long cand = sum - query(K-1) + valans;
        long long cand2 = sum - query(0) + valans;
        if (A <= cand && cand <= 2LL*A) {
            vector<int> idx;
            for (int i=0;i<K-1;i++)idx.push_back(i+1);
            idx.push_back(ans+1);
            answer(idx);
            return;
        }

        if (A <= cand2 && cand2 <= 2LL*A) {
            vector<int> idx;
            for (int i=1;i<K;i++)idx.push_back(i+1);
            idx.push_back(ans+1);
            answer(idx);
            return;
        }

        last = ans-1;
    }

    long long suf = 0;
    for (int i=0;i<K;i++) {
        suf += query(last - i);
    }

    if (A <= suf && suf <= 2LL*A) {
        vector<int> idx;
        for (int i=0;i<K;i++) {
            idx.push_back(last - i + 1);
        }
        answer(idx);
        return;
    }

    if (suf < A) {
        impossible();
        return;
    }

    // now prefix has sum < a, and suffix has sum > 2*a
    // then, there must be a subarray, such that the sum is exactly in between
    // why? because if that wasn't true, then the added contribution must be greater than a
    // however, since all elements are smaller than a, any difference between two elements cannot be greater 
    // that a, hence, there must be a subarray with the desired sum

    l = 0, r = last - K + 1;
    while (l <= r) {
        int m = l + (r-l)/2;

        long long tmpSum = 0;
        for (int i=0;i<K;i++) {
            tmpSum += query(i+m);
        }

        if (A <= tmpSum && tmpSum <= 2LL*A) {
            vector<int> idx;
            for (int i=0;i<K;i++)idx.push_back(i+m+1);
            answer(idx);
            return;
        }

        else if (tmpSum < A) {
            l = m+1;
        }

        else {
            r = m-1;
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20