oj.uz

Submission #401398

# Submission time Handle Problem Language Result Execution time Memory
401398 2021-05-10T06:33:39 Z johutha A Difficult(y) Choice (BOI21_books) C++17
0 / 100
 2 ms 216 KB 
#include <bits/stdc++.h>

#include "books.h"

#define ll long long

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 solve(int N, int K, ll A, int S)
{
    int l = -1;
    int r = N;

    ll lb = 1e18;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        ll v = skim(m + 1);
        if (v >= A) { r = m; lb = min(lb, v); }
        else l = m;
    }

    vector<int> qs;
    for (int i = 0; i < K; i++) qs.push_back(i);
    for (int i = 0; i < K && l - i >= 0; i++) qs.push_back(l - i);
    
    sort(qs.begin(), qs.end());
    qs.erase(unique(qs.begin(), qs.end()), qs.end());

    int m = qs.size();
    vector<ll> vs(m);
    for (int i = 0; i < m; i++) vs[i] = skim(qs[i] + 1);

    for (int i = 0; i < K - 1; i++) lb += vs[i];
    if (A <= lb && lb <= 2*A)
    {
        vector<int> res(K);
        iota(res.begin(), res.end(), 1);
        res[K - 1] = r + 1;
        answer(res);
        return;
    }

    ll cr = 0;
    vector<signed> taken;
    for (int i = 0; i < K; i++)
    {
        taken.push_back(qs[i]);
        cr += vs[i];
    }

    auto check = [&](ll v, vector<int> ind)
    {
        if (v < A || 2*A < v) return false;

        vector<int> res(ind.end() - K, ind.end());
        answer(res);

        return true;
    };

    if (check(cr, taken)) return;

    for (int i = K; i < m; i++)
    {
        cr -= vs[i - K];
        cr += vs[i];
        taken.push_back(qs[i]);
        if (check(cr, taken)) return;
    }
    impossible();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Incorrect 2 ms 204 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Incorrect 2 ms 204 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Incorrect 2 ms 204 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Incorrect 2 ms 204 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Incorrect 2 ms 204 KB Incorrect
9 Halted 0 ms 0 KB -