Submission #1187357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187357		kl0989e	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	1192 KiB

books

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

vl memo(1e5,-1);

ll query(int i) {
	if (memo[i]!=-1) {
		return memo[i];
	}
	return memo[i]=skim(i+1);
}

void solve(int n, int k, ll a, int _) {
	fill(all(memo),-1);
	vl vals(k);
	for (int i=0; i<k; i++) {
		vals[i]=query(i);
	}
	int ans=n;
	int l=0,r=n-1;
	while (l<=r) {
		int m=l+(r-l)/2;
		ll t=query(m);
		if (t<=a) {
			l=m+1;
		}
		else {
			ans=m;
			r=m-1;
		}
	}
	if (ans<k-1) {
		impossible();
	}
	if (ans<n) {
		ll s=accumulate(all(vals),0ll)-vals.back()+query(ans);
		if (a<=s && s<=2*a) {
			vi inds(k);
			iota(all(inds),1);
			inds[k-1]=ans+1;
			answer(inds);
		}
	}
	if (ans==k-1 || accumulate(all(vals),0ll)>2*a) {
		impossible();
	}
	vl vals2(k);
	for (int i=0; i<k; i++) {
		vals2[i]=query(ans-k+i);
	}
	if (accumulate(all(vals2),0ll)<a) {
		impossible();
	}
	vi inds(k);
	iota(all(inds),1);
	ll s=accumulate(all(vals),0ll);
	for (int i=k-1; i>=-1; i--) {
		if (a<=s && s<=2*a) {
			answer(inds);
		}
		s+=vals2[i]-vals[i];
        inds[i]=ans-k+i+1;
	}
	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