답안 #401977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401977	2021-05-11T05:44:47 Z	blue	A Difficult(y) Choice (BOI21_books)	C++17	10 / 100	2 ms	1460 KB

books

#include "books.h"
#include <vector>
#include <algorithm>
using namespace std;

long long n;
long long k;
long long a;

vector<long long> diff(100001);

vector<int> res;
long long curr_sum = 0;

int L, R;

void res_search(long long l, long long books)
{
    // cerr << "rs " << l << ' ' << books << '\n';


    res.push_back(l);
    curr_sum += diff[l];

    if(books-1 == 0)
    {
        if(a <= curr_sum && curr_sum <= 2*a)
            answer(res);

        return;
    }

    for(long long r = l+1; r <= R; r++)
        res_search(r, books-1);

}



void binary_search(long long l, long long r)
{
    // cerr << "bs " << l << ' ' << r << '\n';
    if(l == r)
    {
        L = max(1LL, l-k+1);
        R = min(n, r+k);
        for(long long i = L; i <= R; i++)
            diff[i] = skim(i);

        res_search(L, k);
        impossible();
    }
    else
    {
        long long m = (l+r)/2 + 1;
        if(k*skim(m) <= a*2)
            return binary_search(m, r);
        else
            return binary_search(l, m-1);
    }
}


       //books, choice size, limit,  skim limit
void solve(int N, int K, long long A, int S)
{
    n = N;
    k = K;
    a = A;

    binary_search(1LL, n);
}

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	1 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	2 ms	968 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Incorrect	1 ms	968 KB	Incorrect
7	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	972 KB	Output is correct
2	Correct	1 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	968 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Incorrect	2 ms	968 KB	Incorrect
7	Halted	0 ms	0 KB	-

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	2 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	1068 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	968 KB	Output is correct
7	Correct	1 ms	968 KB	Output is correct
8	Correct	1 ms	968 KB	Output is correct
9	Correct	1 ms	968 KB	Output is correct

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	2 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	1068 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	968 KB	Output is correct
7	Correct	1 ms	968 KB	Output is correct
8	Correct	1 ms	968 KB	Output is correct
9	Correct	1 ms	968 KB	Output is correct
10	Correct	2 ms	968 KB	Output is correct
11	Correct	1 ms	968 KB	Output is correct
12	Correct	2 ms	968 KB	Output is correct
13	Correct	2 ms	968 KB	Output is correct
14	Correct	2 ms	968 KB	Output is correct
15	Correct	1 ms	968 KB	Output is correct
16	Correct	1 ms	968 KB	Output is correct
17	Correct	2 ms	968 KB	Output is correct
18	Correct	2 ms	968 KB	Output is correct
19	Correct	1 ms	968 KB	Output is correct
20	Correct	1 ms	968 KB	Output is correct
21	Correct	1 ms	1080 KB	Output is correct
22	Correct	1 ms	1076 KB	Output is correct
23	Incorrect	2 ms	1460 KB	Incorrect
24	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	2 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	1068 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	968 KB	Output is correct
7	Correct	1 ms	968 KB	Output is correct
8	Correct	1 ms	968 KB	Output is correct
9	Correct	1 ms	968 KB	Output is correct
10	Correct	2 ms	968 KB	Output is correct
11	Correct	1 ms	968 KB	Output is correct
12	Correct	2 ms	968 KB	Output is correct
13	Correct	2 ms	968 KB	Output is correct
14	Correct	2 ms	968 KB	Output is correct
15	Correct	1 ms	968 KB	Output is correct
16	Correct	1 ms	968 KB	Output is correct
17	Correct	2 ms	968 KB	Output is correct
18	Correct	2 ms	968 KB	Output is correct
19	Correct	1 ms	968 KB	Output is correct
20	Correct	1 ms	968 KB	Output is correct
21	Correct	1 ms	1080 KB	Output is correct
22	Correct	1 ms	1076 KB	Output is correct
23	Incorrect	2 ms	1460 KB	Incorrect
24	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	2 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	1068 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	968 KB	Output is correct
7	Correct	1 ms	968 KB	Output is correct
8	Correct	1 ms	968 KB	Output is correct
9	Correct	1 ms	968 KB	Output is correct
10	Correct	2 ms	968 KB	Output is correct
11	Correct	1 ms	968 KB	Output is correct
12	Correct	2 ms	968 KB	Output is correct
13	Correct	2 ms	968 KB	Output is correct
14	Correct	2 ms	968 KB	Output is correct
15	Correct	1 ms	968 KB	Output is correct
16	Correct	1 ms	968 KB	Output is correct
17	Correct	2 ms	968 KB	Output is correct
18	Correct	2 ms	968 KB	Output is correct
19	Correct	1 ms	968 KB	Output is correct
20	Correct	1 ms	968 KB	Output is correct
21	Correct	1 ms	1080 KB	Output is correct
22	Correct	1 ms	1076 KB	Output is correct
23	Incorrect	2 ms	1460 KB	Incorrect
24	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	968 KB	Output is correct
2	Correct	2 ms	968 KB	Output is correct
3	Correct	1 ms	968 KB	Output is correct
4	Correct	1 ms	1068 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	968 KB	Output is correct
7	Correct	1 ms	968 KB	Output is correct
8	Correct	1 ms	968 KB	Output is correct
9	Correct	1 ms	968 KB	Output is correct
10	Correct	2 ms	968 KB	Output is correct
11	Correct	1 ms	968 KB	Output is correct
12	Correct	2 ms	968 KB	Output is correct
13	Correct	2 ms	968 KB	Output is correct
14	Correct	2 ms	968 KB	Output is correct
15	Correct	1 ms	968 KB	Output is correct
16	Correct	1 ms	968 KB	Output is correct
17	Correct	2 ms	968 KB	Output is correct
18	Correct	2 ms	968 KB	Output is correct
19	Correct	1 ms	968 KB	Output is correct
20	Correct	1 ms	968 KB	Output is correct
21	Correct	1 ms	1080 KB	Output is correct
22	Correct	1 ms	1076 KB	Output is correct
23	Incorrect	2 ms	1460 KB	Incorrect
24	Halted	0 ms	0 KB	-