Submission #600697

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

typedef long long ll;

#define All(x) (x).begin(), (x).end()

const ll inf = 1e18, maxn = 1e5 + 10;

ll a[maxn];

// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int k, ll A, int S) {
	int l = 1, r = N;
	while(l < r) {
		int mid = (l + r) >> 1;
		a[mid] = skim(mid);
		if(a[mid] >= A) r = mid;
		else l = mid + 1;
	}

	int pos_A = l;
	a[pos_A] = skim(pos_A);

	if(pos_A < k && a[pos_A] >= A) {
		impossible();
		return;
	}
	if(pos_A == k && a[pos_A] >= A) {
		ll ans = a[pos_A];
		for(int i = 1; i < k; i++) a[i] = skim(i);
		bool flag = false;
		for(int i = 1; i < k; i++) {
			ans += a[i];
			if(ans > inf) {
				flag = true;
				break;
			}
		}
		if(flag) {
			impossible();
		}
		if(ans >= A && ans <= A * 2) {
			vector<int> vc;
			for(int i = 1; i <= k; i++) vc.push_back(i);
			answer(vc);
			return;
		}
		impossible();
		return;
	}

	bool flag = false;
	
	ll ans = 0;
	for(int i = 1; i <= k; i++) {
		a[i] = skim(i), ans += a[i];
		if(ans > inf) {
			flag = true;
			break;
		}
	}
	if(flag) {
		impossible();
		return;
	}

	if(ans >= A && ans <= A * 2) {
		vector<int> vc;
		for(int i = 1; i <= k; i++) vc.push_back(i);
		answer(vc);
		return;
	}
	if(ans > A * 2) {
		impossible();
		return;
	}

	if(a[pos_A] >= A) {
		ans -= a[k], ans += a[pos_A];
		if(ans >= A && ans <= A * 2) {
			vector<int> vc;
			for(int i = 1; i < k; i++) vc.push_back(i);
			vc.push_back(pos_A);
			answer(vc);
			return;
		}
		ans -= a[pos_A], ans += a[k];
	}

	vector<int> vc, vc2;
	for(int i = k; i > 0; i--) vc.push_back(i);
	if(a[pos_A] < A) pos_A++;
	for(int i = pos_A - 1; i > k && !vc.empty(); i--) {
		int ind = pos_A - i;
		a[i] = skim(i);
		ans -= a[ind], ans += a[i];
		if(ans > inf) {
			impossible();
			return;
		}
		vc.pop_back();
		vc2.push_back(i);
		if(ans >= A && ans <= A * 2) {
			vector<int> ans_t;
			for(auto j : vc) ans_t.push_back(j);
			for(auto j : vc2) ans_t.push_back(j);
			sort(All(ans_t));
			answer(ans_t);
			return;
		}
	}

	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