제출 #659807

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

books

#include <bits/stdc++.h>
#include "books.h"
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

//
// --- 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.
//

const int N = 1e5+10;

ll get(int i)
{
	static ll val[N] = {};
	if (!val[i])
		val[i] = skim(i+1);
	return val[i];
}

int n, k;
ll A;

int bin()
{
	int l = 0, r = n;
	while (l < r) {
		int mid = (l+r)/2;
		if (get(mid) >= A)
			r = mid;
		else
			l = mid+1;
	}
	return l;
}

vector<int> make_ans(int l, int r)
{
	vector<int> ans;
	Loop (i,l,r)
		ans.push_back(i+1);
	return ans;
}
vector<int> make_ans(int l, int r, int x)
{
	vector<int> ans;
	Loop (i,l,r)
		ans.push_back(i+1);
	ans.push_back(x+1);
	return ans;
}
vector<int> make_ans(int l, int r, int l2, int r2)
{
	vector<int> ans;
	Loop (i,l,r)
		ans.push_back(i+1);
	Loop (i,l2,r2)
		ans.push_back(i+1);
	return ans;
}

void solve(int _n, int _k, long long _A, int S)
{
	n = _n; k = _k; A = _A;
	int fA = bin();
	if (fA != n) {
		if (fA < k-1) {
			ll sum = 0;
			Loop (i,0,k)
				sum += get(i);
			if (sum > 2*A)
				impossible();
			else
				answer(make_ans(0, k));
			return;
		}
		ll sum = get(fA);
		Loop (i,0,k-1)
			sum += get(i);
		if (A <= sum && sum <= 2*A) {
			answer(make_ans(0, k-1, fA));
			return;
		}
	}
	if (fA >= k) {
		ll sum = 0;
		Loop (i,fA-k,fA)
			sum += get(i);
		if (A <= sum && sum <= 2*A) {
			answer(make_ans(fA-k, fA));
			return;
		}
		if (sum < A) {
			impossible();
			return;
		}
		Loop (i,0,k) {
			sum += get(i);
			sum -= get(fA-k+i);
			if (sum <= 2*A) {
				answer(make_ans(0, i+1, fA-k+i+1, fA));
				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