제출 #600666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600666		Arnch	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	972 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

typedef long long ll;

const int 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;

	if(pos_A < k) {
		impossible();
		return;
	}
	if(pos_A == k) {
		ll ans = a[pos_A];
		for(int i = 1; i < k; i++) a[i] = skim(i);
		for(int i = 1; i < k; i++) ans += a[i];
		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;
	}
	
	ll ans = 0;
	for(int i = 1; i <= k; i++) a[i] = skim(i), ans += a[i];

	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;
	}

	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);
	for(int i = pos_A - 1; i > k; i--) {
		int ind = pos_A - i;
		a[i] = skim(i);
		ans -= a[ind], ans += a[i];
		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);
			answer(ans_t);
			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