Submission #398898

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

void solve(int n, int k, long long goal, int s){
    int lo = 0, hi = n-1, pos;
    while(lo < hi){
        int mid = lo+(hi-lo)/2;
        long long val = skim(mid+1);
        if(val >= goal) hi = mid;
        else lo = mid+1;
    }
    pos = lo; long long val = skim(pos+1);
    if(val < goal) pos = n;

    vector<int> ans;
    vector<long long> arr(n, 0);
    if(pos < k-1){
        impossible();
        return;
    }
    if(pos != n){
        long long sum = 0;
        for(int i = 0; i<k-1; i++) sum += (arr[i] ? arr[i] : arr[i] = skim(i+1));
        if(goal <= sum+val && sum+val <= 2ll*goal){
            for(int i = 0; i<k-1; i++) ans.push_back(i+1);
            ans.push_back(pos+1);
            answer(ans);
            return;
        }
        if(pos == k-1){
            impossible();
            return;
        }
    }
    for(int i = 0; i<k; i++) arr[i] = (arr[i] != 0 ? arr[i] : arr[i] = skim(i+1));
    for(int i = pos-1; i>=pos-k; i--) arr[i] = (arr[i] != 0 ? arr[i] : arr[i] = skim(i+1));
    for(int i = 0; i<=k; i++){
        long long sum = 0;
        for(int j = 0; j<i; j++) sum += arr[j];
        for(int j = pos-1; j>=pos-(k-i); j--) sum += arr[j];
        if(goal <= sum && sum <= 2ll*goal){
            for(int j = 0; j<i; j++) ans.push_back(j+1);
            for(int j = pos-1; j>=pos-(k-i); j--) ans.push_back(j+1);
            answer(ans);
            return;
        }
    }
    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