Submission #918431

#	Time	Username	Problem	Language	Result	Execution time	Memory
918431		TahirAliyev	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	852 KiB

books

#include <bits/stdc++.h>
#include "books.h"

#define ll long long
using namespace std;

const int MAX = 1e5 + 5;
ll arr[MAX];

ll ask(int i){
    if(!arr[i]) arr[i] = skim(i);
    return arr[i]; 
}

void solve(int N, int K, long long A, int S) {
    int l = 1, r = N + 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(ask(mid) < A){
            l = mid + 1;
        }
        else{
            r = mid;
        }
    }
    if(l < K) impossible();
    if(l != N + 1){
        ll sum = 0;
        vector<int> ans;
        for(int i = 1; i < K; i++){
            sum += ask(i);
            ans.push_back(i);
        }
        sum += ask(l);
        ans.push_back(l);
        if(sum <= 2 * A){
            answer(ans);  
        }
    }
    N = l - 1;
    if(N < K) impossible();
    for(int i = 0; i <= K; i++) {
		long long sum = 0;
		vector<int> ans;
		
		for(int j = 1; j <= i; j++){
            sum += ask(j);
            ans.push_back(j);
        } 
		
		for(int j = N - K + i + 1; j <= N; j++){
            sum += ask(j);
            ans.push_back(j);
        } 
 
		if(sum >= A && sum <= 2*A) answer(ans);
	}
    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