Submission #406048

#	Time	Username	Problem	Language	Result	Execution time	Memory
406048		oolimry	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	256 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

lint smallest[14];
void solve(int n, int K, long long A, int S){
	for(int i = 1;i <= K;i++) smallest[i] = skim(i);
	lint X = 0;
	for(int i = 1;i <= K-1;i++) X += smallest[i];
		
	lint low = K-1, high = n+1;
	while(low != high-1){
		lint mid = (low+high)/2;
		lint q = skim(mid);
		if(X + q < A) low = mid;
		else if(X + q > 2*A) high = mid;
		else{
			vector<int> res;
			for(int i = 1;i <= K-1;i++) res.push_back(i);
			res.push_back(mid);
			answer(res);
			return;
		}
	}
	
	if(low == K-1) impossible();
	
	X += smallest[K];
	multiset<int> ress;
	for(int i = 1;i <= K;i++) ress.insert(i);
	for(int i = 1;i <= K;i++){
		X -= smallest[K-i+1];
		X += skim(low-i+1);
		ress.erase(ress.find(K-i+1));
		ress.insert(low-i+1);
		
		if(A <= X and X <= 2*A){
			vector<int> res;
			for(int x : ress) res.push_back(x);
			answer(res);
			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