Submission #659708

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(int n, int k, long long A, int S) {
	int l = 0, r = n + 1;
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		if (skim(mid) <= A) l = mid;
		else r = mid;
	}

	vector<pll> a;
	for (int i = 1; i <= k; i++){
		a.push_back({i, skim(i)});
	}
	ll sum = 0;
	for (auto [x, y]: a) sum += y;
	if (sum > 2*A){
		impossible();
		return;
	}
	if (sum >= A){
		vector<int> res;
		for (auto [x, y]: a) res.push_back(x);
		answer(res);
		return;
	}
	if (l >= k){
		vector<pll> b;
		for (int i = l-k+1; i <= l; i++){
			b.push_back({i, skim(i)});
		}
		ll tmp = 0;
		for (auto [x, y]: b) tmp += y;
		if (tmp >= A){
			vector<int> res;
			while(sum < A){
				res.push_back(b.back().F);
				sum += b.back().S - a.back().S;
				b.pop_back();
				a.pop_back();
			}
			for (auto [x, y]: a) res.push_back(x);
			answer(res);
			return;
		}
	}
	if (r <= n){
		sum += skim(r) - a.back().S;
		a.pop_back();
		if (sum <= 2 * A){
			vector<int> res;
			for (auto [x, y]: a) res.push_back(x);
			res.push_back(r);
			answer(res);
			return;
		}
	}
	impossible();
	return;
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:41:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |  for (auto [x, y]: a) sum += y;
      |            ^
books.cpp:48:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |   for (auto [x, y]: a) res.push_back(x);
      |             ^
books.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   for (auto [x, y]: b) tmp += y;
      |             ^
books.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |    for (auto [x, y]: a) res.push_back(x);
      |              ^
books.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |    for (auto [x, y]: a) res.push_back(x);
      |              ^

• 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