Submission #464022

#	Time	Username	Problem	Language	Result	Execution time	Memory
464022		AriaH	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	17 ms	328 KiB

books

/** work as hard as you can and keep the first place **/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "books.h"

using namespace std;

typedef long long			ll;
typedef long double			ld;
typedef pair < int, int > 	pii;
typedef pair < ll, ll > 	pll;

#define F					first
#define S					second
#define all(x)				x.begin(), x.end()
#define SZ(x)				(int)x.size()
#define Mp					make_pair

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }

map < ll, ll > mp;

/*ll skim(int i)
{
	return 1;
}*/

ll ask(int i)
{
	if(mp.count(i))
	{
		return mp[i];
	}
	return mp[i] = skim(i);
}

/*void answer(vector < int > vec)
{

}

void impossible()
{

}
*/

void solve(int n, int k, ll A, int s)
{
	mp.clear();
	int d = 0, up = n + 1;
	while(up - d > 1)
	{
		int mid = (up + d) >> 1;
		if(ask(mid) < A) d = mid;
		else up = mid;
	}
	if(up > n) up --;
	if(up < k) impossible();
	vector < pll > vec;
	for(int i = 1; i <= min(k, up - k); i ++)
	{
		vec.push_back(Mp(ask(i), i));
	}
	for(int i = up - k + 1; i <= up; i ++)
	{
		vec.push_back(Mp(ask(i), i));
	}
	sort(all(vec));
	int sz = SZ(vec);
	for(int mask = 0; mask < 1 << sz; mask ++)
	{
		if(__builtin_popcount(mask) != k) continue;
		ll sum = 0;
		for(int i = 0; i < sz; i ++)
		{
			if(mask >> i & 1)
			{
				sum += vec[i].F;
			}
		}
		if(A <= sum && sum <= 2ll * A)
		{
			vector < int > ret;
			for(int i = 0; i < sz; i ++)
			{
				if(mask >> i & 1) ret.push_back(vec[i].S);
			}
			answer(ret);
			return;
		}
	}
	impossible();
}

/*int main()
{
	return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/

• 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