제출 #415080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415080		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	8 ms	316 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 ksum = 0;
	for(int i=1;i<k;i++) get(i), ksum += a[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){
					if(ksum + a[i] >= A && ksum + a[i] <= 2 * A){
						vector<i32> rr = res(1, k-1);
						rr.pb(i); answer(rr); return; 
					} break;
				} answer(res(i - k + 1, i)); 
				return;
			} sum -= a[i-k+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