Submission #433117

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

books

#include <bits/stdc++.h>
#include "books.h"
#define ll long long
 
using namespace std;
 
void solve(int N, int K, ll A, int S){
	int x = 0;
	for(int y=1<<19; y/=2; )
		if(x + y <= N && skim(x + y) < A) x += y;
	++x;
 
	vector<pair<int, ll>> vals;
	for(int i=1; i<=K; ++i) vals.emplace_back(i, skim(i));
	for(int i=max(K+1, x-K); i<x; ++i) vals.emplace_back(i, skim(i));
 
	if(x<=N) vals.emplace_back(x, skim(x));
 
	for(int i=1; i<=K+K; ++i){
		if(i+K-1 > (int)vals.size()) break;
		ll sum = 0;
		vector<int> res(K);
		for(int j=0; j<K; ++j) sum += vals[i+j-1].second, res[j] = vals[i+j-1].first;
		if(A<=sum && sum<=A+A) return answer(res);
	}
 
	if(x <= N){
		ll sum = 0;
		vector<int> res(K);
		for(int i=1; i<K; ++i) sum += vals[i-1].second, res[i-1] = i;
		sum += skim(x);
		res[K-1] = x;
		if(A<=sum && sum<=A+A) return answer(res);
	}
	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