Submission #1187301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187301		kl0989e	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1 ms	804 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()

vi memo(1e5,-1);
int n;

int query(int i) {
	if (i<0 || i>=n) {
		exit(-1);
	}
	if (memo[i]!=-1) {
		return memo[i];
	}
	memo[i]=skim(i+1);
	return memo[i];
}

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