Submission #434970

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

long long cache[100005];

long long skimming(int id) {
	if(cache[id]!=0)
		return cache[id];
	return cache[id]=skim(id);
}

void solve(int N, int K, long long A, int S) {
	long long sum=0;
	for(int i=1;i<K;i++)
		sum+=skimming(i);
	if(sum>2*A)
		impossible();
	vector<int> rs;
	for(int i=1;i<K;i++)
		rs.push_back(i);
	int l=K,r=N,pivot=-1;
	while(l<=r) {
		int mid=(l+r)/2;
		if(A<=sum+skimming(mid)&&sum+skimming(mid)<=2*A) {
			rs.push_back(mid);
			answer(rs);
		}
		if(sum+skimming(mid)<A) {
			pivot=mid;
			l=mid+1;
		} else
			r=mid-1;
	}
	if(pivot==-1)
		impossible();
	int cnt=0;
	for(int i=rs.size()-1;i>=0;i--) {
		sum-=skimming(rs[i]);
		cnt++;
		sum+=skimming(pivot-cnt);
		rs[i]=pivot-cnt;
		if(A<=sum+skimming(pivot)&&sum+skimming(pivot)<=2*A) {
			rs.push_back(pivot);
			answer(rs);
		}
	}
	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