oj.uz

Submission #946032

# Submission time Handle Problem Language Result Execution time Memory
946032 2024-03-14T09:44:57 Z Pikachu A Difficult(y) Choice (BOI21_books) C++17
0 / 100
 1 ms 1368 KB 
#include <bits/stdc++.h>

#include "books.h"

using namespace std;

void solve(int n, int k, long long A, int s)
{
    vector<long long> a(n + 2, -1);
    long long sum = 0;
    for (int i = 1; i <= k; i++) {
        a[i] = skim(i);
        sum += a[i];
    }
    if (sum > 2ll * A) impossible();
    if (sum >= A) {
        vector<int> ans;
        for (int i = 1; i <= k; i++) ans.push_back(i);
        answer(ans);
    }
    int l = 1, r = n, oe = n + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (skim(mid) >= A) {
            oe = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if (oe != n + 1) {
        if (sum - a[k] + a[oe] <= 2ll * A) {
            vector<int> ans;
            for (int i = 1; i < k; i++) {
                ans.push_back(i);
            }
            ans.push_back(oe);
            answer(ans);
        }
    }
    oe--;
    long long dak = 0;
    for (int i = oe; i > oe - k; i--) {
        a[i] = skim(i);
        dak += a[i];
    }
    if (dak < A) impossible();
    for (int i = oe; i > oe - k; i--) {
        vector<int> ans;
        int lef = k - (oe - i + 1);
        int sum = 0;
        for (int j = k - lef + 1; j <= k; j++) {
            ans.push_back(j);
            sum += a[j];
        }
        for (int j = i; j <= oe; j++) {
            ans.push_back(j);
            sum += a[j];
        }
        if (A <= sum && sum <= 2ll * A) {
            answer(ans);
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 572 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1196 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Incorrect 1 ms 1112 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1196 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Incorrect 1 ms 1112 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1196 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Incorrect 1 ms 1112 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1196 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Incorrect 1 ms 1112 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1196 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 1 ms 1368 KB Output is correct
8 Incorrect 1 ms 1112 KB Incorrect
9 Halted 0 ms 0 KB -