Submission #1224643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224643		midi	A Difficult(y) Choice (BOI21_books)	C++20	10 / 100	3 ms	1232 KiB

books

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

typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll,ll> prll;
#define umap unordered_map

#define fi first
#define se second
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(a); (i)>=(a); (i)--)
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define sz size

#define mxN (100010ll)
#define INF (LLONG_MAX-100ll)

// skim(3);
// impossible();
// answer({1,3});

ll n, k, A, A2, big;
vcll ar(mxN,-1);

inline ll peak (ll i) { return ar[i]==-1 ? skim(i) : ar[i]; }

inline ll find_big()
{
	ll l=1, r=n, big2=n+1;
	while (l<=r)
	{
		ll mid=(l+r)/2;
		if (peak(mid)>A)
		{
			big2=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	return big2;
}

inline vc<int> rng (vcll a, ll l, ll r)
{
	vc<int> res;
	ll i;
	f0r(i,l,r) res.pb(a[i]);
	return res;
}

inline vc<int> normrng (ll l, ll r)
{
	vc<int> res;
	ll i;
	f0r(i,l,r) res.pb(i);
	return res;
}

inline vc<int> merge (vc<int> a, vc<int> b)
{
	vc<int> res;
	for (ll x:a) res.pb(x);
	for (ll x:b) res.pb(x);
	return res;
}

inline vc<int> bf (vc<int> inds1)
{
	vcll inds;
	for (ll x:inds1) inds.pb(x);
	ll k1=inds.sz();
	if (k1<k) return {};
	vcll nums;
	nums.pb(-1);
	for (ll i:inds) nums.pb(peak(i));
	ll s=0, i;
	f0r(i,1,k) s+=nums[i];
	if (A<=s and s<=A2) return rng(inds,0,k-1);
	f0r(i,i,k1)
	{
		s += nums[i] - nums[i-k];
		if (A<=s and s<=A2) return rng(inds,i-k,i-1);
	}
	return {};
}

void solve(int N1, int K1, long long A1, int S1)
{
	n=N1; k=K1; A=A1; A2=2*A;
	if (n<=S1)
	{
		vc<int> ans=bf(normrng(1,n));
		if (ans.sz()) answer(ans);
		impossible();
	}
	big=find_big();
	if (big==n+1)
	{
		ar[big]=INF;
	}
	if (big==1)
	{
		if (peak(big<=A2) and k==1) answer({1});
		impossible();
	}
	if (big-1<=20)
	{
		vc<int> ans=bf(normrng(1,big-1));
		if (ans.sz()) answer(ans);

		A-=peak(big);
		A2-=peak(big);
		if (A2<=0) impossible();
		ans=bf(normrng(1,big-1)); // TODO
		if (ans.sz())
		{
			ans.pb(big);
			answer(ans);
		}
		impossible();
	}

	// edge cases

	vc<int> inds = merge(normrng(1,k), normrng(big-k,big-1));
	vc<int> ans=bf(inds);
	if (ans.sz()) answer(ans);
	A-=peak(big);
	A2-=peak(big);
	if (A2<=0) impossible();
	ans=bf(inds);
	if (ans.sz())
	{
		ans.pb(big);
		answer(ans);
	}
	impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20