Submission #725500

#	Time	Username	Problem	Language	Result	Execution time	Memory
725500		josanneo22	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	5 ms	208 KiB

books

#include <bits/stdc++.h> 
#include "books.h"
using namespace std;
int arr[200005], arr2[200005];
void solve(int N, int K, long long A, int S) {
	int n = N,  k = K, a = A, s = S;
	for (int i = 1; i <= k; i++) {
		arr[i]=skim(i);
	}
	int mn = 1, mx = n, loc = n + 1;
	long long val = 1e18;
	while (mn <= mx) {
		int mid = (mx + mx) / 2;
		long long tmp = skim(mid);
		if (tmp >= a) {
			val = tmp;
			loc = mid;
			mx = mid - 1;
		}
		else mn = mid + 1;
	}
	if (loc != n + 1) {
		long long sum = 0;
		for (int i = 1; i < k; i++) sum += arr[i];
		sum += val;
		if (A <= sum && sum <= A + A) {
			vector<int> v;
			for (int i = 1; i < k; i++) v.push_back(i);
			v.push_back(loc);
			answer(v);
			return;
		}
	}

	loc--;
	if (loc < k) impossible();

	for (int i = 1; i <= k; i++) {
		arr2[i] = skim(loc + 1 - i);
	}

	for (int i = 0; i <= k; i++) {
		long long sum = 0;
		for (int j = 1; j <= i; j++) sum += arr[j];
		for (int j = 1; j <= k - i; j++) sum += arr2[j];
		if (A <= sum && sum <= A + A) {
			vector<int> v;
			for (int j = 1; j <= i; j++) v.push_back(j);
			for (int j = 1; j <= k - i; j++) v.push_back(loc + 1 - j);
			answer(v);
			return;
		}
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:6:28: warning: unused variable 's' [-Wunused-variable]
    6 |  int n = N,  k = K, a = A, s = S;
      |                            ^

• 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