Submission #720183

#	Time	Username	Problem	Language	Result	Execution time	Memory
720183		Johann	A Difficult(y) Choice (BOI21_books)	C++14	45 / 100	2 ms	296 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define mll map<ll,ll>

// Ab hier








void answer2(vi & sol) {
    for (int i = 0; i < sol.size(); ++i) ++sol[i];
    answer(sol);
}
ll ask(int i, mll & store) {
    if (store.find(i) == store.end()) store[i] = skim(i+1);
    return store[i];
}


int lowerBound(ll v, mll & store, int l, int r) {
    int m;
    while ( l < r ) {
        m = (l + r) / 2;
        if (ask(m, store) < v) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return l;
}
int lowerBound(ll v, mll & store, int N) {
    return lowerBound(v, store, 0, N-1);
}

void solve(int N, int K, ll A, int S) {
    mll store;
    vi sol;
    int i = lowerBound(A, store, N);
    ll xi = ask(i, store);
    if (i < K-1) { impossible(); return; }
    ll sum = 0;
    for (int j = 0; j < K-1; ++j) sum += ask(j, store);
    if (A <= sum + xi && sum + xi <= 2*A) {
        for (int k = 0; k < K-1; ++k) sol.push_back(k);
        sol.push_back(i);
        answer2(sol);
        return;
    }

    ll lower = ceil((double) A / K);
    ll upper = floor( (double) 2 * A / K);
    int l = lowerBound(lower, store, 0, i);
    int r = lowerBound(upper, store, l, i);
    if (ask(r, store) > upper) --r;

    int dist = r - l + 1;
    if (dist >= K) {
        for (int k = 0; k < K; ++k) sol.push_back(l + k);
        answer2(sol);
        return;
    } else {
        l = max(0, min(l - dist, N - K));
        r = l + K ; // r als [l, r)
        sum = 0;
        for (int j = l; j < r; ++j) sum += ask(j, store);
        while (r < N && sum <= 2 * A) {
            if (A <= sum) {
                for (int k = 0; k < K; ++k) sol.push_back(l + k);
                answer2(sol);
                return;
            }
            sum -= ask(l++, store);
            sum += ask(r++, store);
        }
        if (A <= sum && sum <= 2 * A) {
            for (int k = 0; k < K; ++k) sol.push_back(l + k);
            answer2(sol);
            return;
        }
    }

    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void answer2(std::vector<int>&)':
books.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < sol.size(); ++i) ++sol[i];
      |                     ~~^~~~~~~~~~~~

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