Submission #944165

#	Time	Username	Problem	Language	Result	Execution time	Memory
944165		siewjh	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1364 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll vals[MAXN];
ll getv(int x){
	if (vals[x] != -1) return vals[x];
	else return vals[x] = skim(x);
}
void solve(int N, int K, ll A, int S) {
    memset(vals, -1, sizeof(vals));
    vector<int> ans;
    ll sum = 0;
    for (int i = 1; i <= K; i++) sum += getv(i);
    if (sum > 2 * A) impossible();
    sum -= getv(K);
    int l = K, r = N, res = N + 1;
    while (l <= r){
		int m = (l + r) >> 1;
		if (sum + getv(m) >= A){
			res = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	if (res != N + 1){
		if (sum + getv(res) <= 2 * A){
			for (int i = 1; i < K; i++) ans.push_back(i);
			ans.push_back(res);
			answer(ans);
		}
	}
	sum += getv(K);
	for (int i = 1; i <= K; i++){
		sum += getv(res - i); sum -= getv(K + 1 - i);
		if (sum >= A){
			for (int j = 1; j <= K - i; j++) ans.push_back(j);
			for (int j = res - i; j < res; j++) ans.push_back(j);
			answer(ans);
		}
	}
	impossible();
}

• 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