Submission #551883

#	Time	Username	Problem	Language	Result	Execution time	Memory
551883		keta_tsimakuridze	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	1 ms	680 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> get(int L, int R) {
	vector<int> v;
	for(int i = L; i <= R; i++) v.push_back(i + 1);
	return v;
}
void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    int l = 0, r = N - 1, x = N, val = 0 ;
	while(l <= r) {
		int mid = (l + r) / 2;
		int a = skim(mid + 1);
		if(a >= A) x = mid, val = a, r = mid - 1;
		else l = mid + 1;
	} 
	vector<int> a(N);
	for(int i = 0; i < K; i++) a[i] = skim(i + 1);
	for(int i = x - 1; i >= max(0, x - K); i--) a[i] = skim(i + 1);
	int sum0 = 0;
	for(int i = 0; i < K; i++) {
		sum0 += a[i];
	}
	if(sum0 > 2 * A)  {
		impossible();
		return;
	}
	if(sum0 >= A) {
		vector<int> v;
		for(int i = 0; i < K; i++) {
			v.push_back(i);
		}
		answer(v);
		return ;
	}
	if(x < N && val + sum0 - a[K - 1] <= 2 * A) {
		vector<int> v = get(0, K - 2);
		v.push_back(x + 1);
		answer(v);
		return;
	}
	for(int i = K; i < x; i++) {
		sum0 += a[i] - a[i - K];
		if(sum0 >= A) {
			answer(get(i - K + 1, i));
			return;
		}
	}
	impossible();
}

• 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