Submission #1157582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157582		minh30082008	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	19 ms	1192 KiB

books

#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
//#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "chinaflu.inp"
#define output "chinaflu.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 9;
const int base = 998244353;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rd);
}

#include<vector>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cstdarg>
#include<cassert>
#include"books.h"

using namespace std;

typedef long long ll;

ll a[maxn];
void solve(int n, int k, ll A, int S)
{
	FOR(i, 1, n)
		a[i] = -1;
	FOR(i, 1, k)
		a[i] = skim(i);
	int l = 1, r = n, vt = -1;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(a[mid] == -1)
			a[mid] = skim(mid);
		if(a[mid] >= A)
			vt = mid, r = mid - 1;
		else
			l = mid + 1;
	}
	if(vt == -1)
		vt = n;
	int cnt = 0;
	vll vv;
	FOR(i, 1, k)
		vv.pb(i);
	while(cnt <= k && vt)
	{
		if(a[vt] != -1)
		{
			a[vt] = skim(vt);
		}
		cnt++;
		vv.pb(vt);
		vt--;
	}
	FOR(mask, 1, (1 << vv.size()) - 1)
	{
		if(__builtin_popcount(mask) != k)
			continue;
		ll sum = 0;
		FOR(i, 0, vv.size() - 1)
			if((mask >> i) & 1)
				sum += a[vv[i]];
		if(sum >= A && sum <= 2 * A)
		{
			vi ans;
			FOR(i, 0, vv.size() - 1)
				if((mask >> i) & 1)
					ans.pb(vv[i]);
			answer(ans);
		}
	}
	impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20