Submission #652367

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

books

#include "books.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

int bin(int n, int k, ll a)
{
	int l=0, r=n-k;
	while (l < r) {
		int m = (l+r)/2;
		if (skim(m+1)*k >= a)
			r = m;
		else
			l = m+1;
	}
	return l;
}

const int N = 1e5+10;
ll x[N];

void solve(int n, int k, long long a, int s)
{
	int i = bin(n, k, a);
	int bak = -1;
	ll sum = 0;
	Loop (j,i,i+k) {
		x[j] = skim(j+1);
		sum += x[j];
		if (x[j] > a) {
			bak = i+k-1-j;
			break;
		}
	}
	if (bak != -1) {
		i -= bak;
		if (i < 0) {
			impossible();
			return;
		}
		Loop (j,i,i+bak) {
			x[j] = skim(j+1);
			sum += x[j];
		}
	}
	if (sum < a) {
		impossible();
		return;
	}
	if (sum <= 2*a) {
		vector<int> ans(k);
		iota(ans.begin(), ans.end(), i+1);
		answer(ans);
		return;
	}
	int fail = -1;
	for (int j = i-1; j >= 0; --j) {
		x[j] = skim(j+1);
		sum += x[j];
		sum -= x[j+k];
		if (sum < a) {
			fail = j;
			break;
		}
		if (sum <= 2*a) {
			vector<int> ans(k);
			iota(ans.begin(), ans.end(), j+1);
			answer(ans);
			return;
		}
	}
	if (fail == -1) {
		impossible();
		return;
	}
	i = fail+k;
	assert(x[i] >= a);
	sum = x[i];
	Loop (j,0,k-1)
		sum += skim(j+1);
	if (sum <= 2*a) {
		vector<int> ans(k);
		iota(ans.begin(), ans.end(), 1);
		ans[k-1] = i+1;
		answer(ans);
		return;
	} else {
		impossible();
		return;
	}
}

• 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