Submission #807169

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

books

// In the name of Allah
 
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
 
typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
 
#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0)
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);
 
const int maxn = 1e6 + 4;
ll arr[maxn]; set<int> res;
 
void answerx() {
	vector<int> vc;
	for (int i : res) vc.pb(i);
	answer(vc);
}
 
void solve(int N, int K, ll A, int S) {
	ll sm = 0;
	for (int i = 1; i <= K; i++) {
		arr[i] = skim(i); sm += arr[i];
		res.insert(i);
	}
	
	if (sm >= A && sm <= 2 * A) answerx();
	else if (sm > 2 * A) impossible();
	
	sm -= arr[K]; res.erase(K);
	int l = K, r = N + 1;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		arr[mid] = skim(mid);
		
		if (sm + arr[mid] <= 2 * A) l = mid;
		else r = mid;
	}
	sm += arr[l]; res.insert(l);
	
	int i = K - 1, j = l - 1;
	while (i >= 1 && (sm < A || sm > 2 * A)) {
		arr[j] = skim(j);
		sm -= arr[i]; res.erase(i); i--;
		sm += arr[j]; res.insert(j); j--;
	}
	
	if (sm >= A && sm <= 2 * A) answerx();
	else 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