Submission #408661

#	Time	Username	Problem	Language	Result	Execution time	Memory
408661		ly20	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1068 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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.
//
const int MAXN = 112345;
long long qr[MAXN];
long long val(int a) {
    if(qr[a] == -1) qr[a] = skim(a);
    return qr[a];
}
long long ts(int a, int b, int c, int d) {
    long long tst = 0;
    for(int i = a; i <= b; i++) tst += val(i);
    for(int i = c; i <= d; i++) tst += val(i);
    return tst;
}
void solve(int n, int k, long long a, int s) {
    // TODO implement this function
    for(int i = 1; i <= n; i++) qr[i] = -1;
    int ini = 1, fim = n;
    while(ini < fim) {
        int m = (ini + fim) / 2;
        //if(ini == fim - 1) m = fim;
        if(val(m) >= a) fim = m;
        else ini = m + 1;
    }
    long long vlm = val(fim);
    if(val(fim) < a) {
        fim = n + 1;
        ini = n + 1;
        vlm = 1123456789012345678;
    }
    if(ts(1, k, 0, -1) > 2 * a) impossible();
    else if(ts(1, k, 0, -1) >= a) {
        vector <int> temp;
        for(int i = 1; i <= k; i++) temp.push_back(i);
        answer(temp);
    }
    if(ts(1, k - 1, 0, -1) + vlm <= 2 * a) {
        vector <int> temp;
        for(int i = 1; i < k; i++) temp.push_back(i);
        temp.push_back(ini);
        answer(temp);
    }
    if(ini - 1 < k) impossible();
    for(int i = 0; i <= k; i++) {
            if(ini - k + 1 < 1) continue;
        if(ts(1, i, ini - k + i, ini - 1) <= 2 * a && ts(1, i, ini - k + i, ini - 1) >= a) {
            vector <int> temp;
            for(int j = 1; j <= i; j++) temp.push_back(j);
            for(int  j = ini - k + i; j < ini; j++) temp.push_back(j);
            answer(temp);
        }
    }
    impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20