oj.uz

Submission #950105

# Submission time Handle Problem Language Result Execution time Memory
950105 2024-03-20T05:26:01 Z Pring A Difficult(y) Choice (BOI21_books) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>

#include "books.h"

using namespace std;
using ll = long long;
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)

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

const int MXN = 100005;
ll h[MXN];

int SKIM(int id) {
    if (h[id] != 0) return h[id];
    return (h[id] = skim(id));
}

int BSH(int l, int r, ll a) {
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        (SKIM(mid) >= a ? r : l) = mid;
    }
    return r;
}

bool check1(int n, int k, ll a) {
    int acc = 0;
    FOR(i, 1, k + 1) acc += h[i];
    if (acc < a) return false;
    if (acc <= 2 * a) {
        vector<int> v;
        FOR(i, 1, k + 1) v.push_back(i);
        answer(v);
        return true;
    }
    impossible();
    return true;
}

void solve(int n, int k, ll a, int s) {
    // cout << n << ' ' << k << ' ' << a << endl;
    FOR(i, 1, k + 1) h[i] = SKIM(i);
    if (h[k] >= a) {
        ll acc = 0;
        FOR(i, 1, k + 1) acc += h[i];
        if (a <= acc && acc <= 2 * a) {
            vector<int> v;
            FOR(i, 1, k + 1) v.push_back(i);
            answer(v);
            return;
        }
        impossible();
        return;
    }
    if (check1(n, k, a)) return;
    ll acc = 0;
    FOR(i, 1, k + 1) acc += h[i];
    int aa = n + 1;
    h[n] = SKIM(n);
    if (acc - h[k] + h[n] >= a) {
        acc -= h[k];
        int x = BSH(k, n + 1, a - acc);
        if (x != n + 1) {
            h[x] = SKIM(x);
            if (acc + h[x] <= 2 * a) {
                vector<int> v;
                FOR(i, 1, k) v.push_back(i);
                v.push_back(x);
                answer(v);
                return;
            }
        }
        aa = x;
    }
    ll ans = 0;
    FOR(i, 1, k + 1) ans += h[i];
    for (int i = k; i > 0; i--) {
        int id = aa - (k - i) - 1;
        h[id] = SKIM(id);
        ans -= h[i];
        ans += h[id];
        if (ans >= a) {
            ans -= h[id];
            int bb = BSH(k - 1, id, a - ans);
            vector<int> v;
            FOR(j, 1, i) v.push_back(j);
            v.push_back(bb);
            FOR(j, id + 1, aa) v.push_back(j);
            answer(v);
            return;
        }
    }
    impossible();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -