제출 #1297153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297153		cowkim	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1 ms	400 KiB

books

#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.
//
ll doquery(int i, map<int,ll>& storeRes){
    if(storeRes.find(i) != storeRes.end()){
        return storeRes[i];
    }
    else{
        return storeRes[i] = skim(i);
    }
}
void solve(int N, int K, long long A, int S) {
    map<int,ll> storeRes;
    //find the first element such that Kfirst + x >= A
    ll firstKm1 = 0;
    for(int i = 1; i < K; i++){
        firstKm1 += doquery(i,storeRes);
    }
    int l = K-1;
    int r = N+1;
    while(l+1 < r){
        int mid = (l+r)/2;
        ll res = doquery(mid,storeRes);
        if(res + firstKm1 < A) l = mid;
        else r = mid;
    }
    if(r != N+1){
        if(r + firstKm1 <= 2*A){
            vector<int> ans(K);
            ans[K-1] = r;
            for(int i = 1; i< K; i++){
                ans[i-1] = i;
            }
        }
    }
    //ta från bakom tills det blir mer än A
    int first = l;
    ll pref = 0;
    if(l < K){
        impossible();
        return;
    }
    for(int i = 1; i <= K; i++){
        pref += doquery(first - i + 1,storeRes);
        if(pref >= A){
            vector<int> ans;
            for(int j = 1; j<= K- j; j++){
                ans.push_back(j);
            }
            for(int j = first-i +1; j <= first; j++){
                ans.push_back(j);
            }
            answer(ans);
            return;
        }
    }
    impossible();
}

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