Submission #646316

#TimeUsernameProblemLanguageResultExecution timeMemory
646316alextodoranA Difficult(y) Choice (BOI21_books)C++17
Compilation error
0 ms0 KiB
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll skim (int i);
void answer (vector <int> v);
void impossible ();

void solve (int N, int K, ll A, int S) {
    ll D[N + 1];
    int l = 1, r = N + 1;
    while (l < r) {
        int mid = (l + r) / 2;
        D[mid] = skim(mid);
        if (D[mid] > A) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    for (int i = 1; i <= min(l - 1, K); i++) {
        D[i] = skim(i);
    }
    for (int i = max(1, l - K); i <= min(N, l); i++) {
        D[i] = skim(i);
    }
    if (l < K) {
        impossible();
        return;
    }
    if (l <= N) {
        ll sum = D[l];
        for (int i = 1; i <= K - 1; i++) {
            sum += D[i];
        }
        if (sum <= A * 2) {
            vector <int> v(K);
            iota(v.begin(), v.end() - 1, 1);
            v.back() = l;
            answer(v);
            return;
        }
    }
    if (l - 1 < K) {
        impossible();
        return;
    }
    ll sum = 0;
    for (int i = 1; i <= K; i++) {
        sum += D[i];
    }
    vector <int> L(K), R;
    iota(L.begin(), L.end(), 1);
    for (int i = K; i >= 1 && sum < A; i--) {
        sum -= D[L.back()];
        R.push_back(l - 1 + i - K);
        sum += D[R.back()];
    }
    if (sum < A) {
        impossible();
        return;
    }
    vector <int> v = L;
    reverse(R.begin(), R.end());
    for (int i : R) {
        v.push_back(i);
    }
    answer(v);
}

int N = 7, K = 3, A = 23;
ll D[] = {1, 1, 4, 6, 12, 32, 35};
ll skim (int i) {
    return D[i - 1];
}
void answer (vector <int> v) {
    for (int i : v) {
        cout << i << " ";
    }
    cout << "\n";
}
void impossible() {
    cout << "Impossible\n";
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve(N, K, A, 40);

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccYY8KsP.o: in function `answer(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0xa0): multiple definition of `answer(std::vector<int, std::allocator<int> >)'; /tmp/ccuCP6YQ.o:books.cpp:(.text+0x20): first defined here
/usr/bin/ld: /tmp/ccYY8KsP.o: in function `impossible()':
grader.cpp:(.text+0x160): multiple definition of `impossible()'; /tmp/ccuCP6YQ.o:books.cpp:(.text+0x90): first defined here
/usr/bin/ld: /tmp/ccYY8KsP.o: in function `skim(int)':
grader.cpp:(.text+0x1a0): multiple definition of `skim(int)'; /tmp/ccuCP6YQ.o:books.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/ccYY8KsP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuCP6YQ.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status