Submission #415078

#	Time	Username	Problem	Language	Result	Execution time	Memory
415078		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	6 ms	308 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];
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) {
	int l = 1, r = n, s = -1;
	while(l + 1 < r){
		int m = (l + r + 1)>>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 = max((int)n, s + k - 1);
	for(int i=l;i<=r;i++) get(i);
	int sum = 0;
	for(int i=l;i<=r;i++){
		sum += a[i];
		if(i - l + 1 >= k){
			if(A <= sum){
				if(sum > 2 * A) break;
				answer(res(i - k + 1, i)); 
				return;
			} sum -= a[i-k+1];
		}
	}

	sum = 0;
	for(int i=1;i<k;i++) get(i), sum += a[i];
	vector<i32> rr = res(1, k-1);
	
	l = 1, r = n;
	while(l < r){
		int m = (l + r)>>1;
		get(m);
		if(sum + a[m] >= A && sum + a[m] <= 2*A){
			vector<i32> res;
			for(int l=1;l<k;l++) res.pb(l);
			res.pb(m); answer(res); return; 
		} if(sum + a[m] < A) l = m+1;
		if(sum + a[m] > 2*A) r = m - 1;
	}
	
	impossible();
	return;
}

/*
 
4 3 20 5
5 10 17 25

*/

• 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