Submission #415099

#	Time	Username	Problem	Language	Result	Execution time	Memory
415099		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	3 ms	456 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;	

#define int long long
#define i32 int32_t
#define pb push_back
#define ff first
#define ss second

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
template<int sz> using tut = array<int, sz>;

const int M = 2e5+5;
const long long inf = 1e18;
const int mod = 1e9+7;
int a[M], pref[M], n;
bitset<M> used;

void get(int m){
	if(used[m]) return;
	a[m] = skim(m), used[m] = 1;
}

vector<i32> res(int l, int r){
	vector<i32> rr;
	for(int i=l;i<=r;i++) rr.pb(i);
	return rr;
}

void solve(i32 n, i32 k, int A, i32 S) {
	::n = n;
	int l = 1, r = n, s = -1;
	while(l + 1 < r){
		int m = (l + r)>>1; get(m);
		if(k * a[m] < A) l = m;
		else if(k * a[m] > 2 * A) r = m;
		else { s = m; break; }
	} if(s == -1) s = l;
	
	l = max(1ll, s - k + 1), r = min((int)n, s + k - 1);
	for(int i=l;i<=r;i++) get(i);
	int in = -1, sum = 0;
	for(int i=l;i<l+k;i++) sum += a[i];
	if(sum >= A && sum <= 2 * A) { answer(res(l, l+k-1)); return; }
	for(int i=l+k;i<=r;i++){
		sum -= a[i-k], sum += a[i];
		if(sum >= A) { in = i; break; }
	} if(sum >= A && sum <= 2 * A) { answer(res(in-k+1, in)); return; }
	sum = a[in];
	for(int i=1;i<k;i++) get(i), sum += a[i];
	vector<i32> rr; rr = res(1, k-1); rr.pb(in);
	if(sum >= A && sum <= 2 * A) answer(rr); 
	else impossible(); 
}

/*
 
4 3 20 5
5 10 17 25

*/

• 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