Submission #415885

#	Time	Username	Problem	Language	Result	Execution time	Memory
415885		Blagojce	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	49 ms	328 KiB

books

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;

#include "books.h"

ll pref[10];

vector<pair<ll,int> > v;


void iter(ll A, int K){
	fr(mask, 0, (1<<((int)v.size()))){
		if(__builtin_popcount(mask) != K) continue;
		
		ll sum = 0;
		fr(j, 0, (int)v.size()){
			if(mask&(1<<j)) sum += v[j].st;
		}
		if(A <= sum && sum <= 2*A){
			vector<int> sol;
			fr(j, 0, (int)v.size()){
				if(mask&(1<<j))sol.pb(v[j].nd+1);
			}
			answer(sol);
		}
	}
	impossible();
}



void solve(int N, int K, long long A, int S) {
	if(N <= 10){
		fr(i, 0, N){
			v.pb({skim(i+1), i});
		}
		iter(A, K);
	}
	else{
		fr(i, 0, 10){
			pref[i] = skim(i+1);
			v.pb({pref[i], i});
		}
		if(pref[0] < A){
			
			int l = 0;
			int r = N-1;
			while(l < r){
				int mid = (l + r + 1)/2;
				ll val = skim(mid+1);
				if(val < A){
					l = mid;
				}
				else{
					r = mid-1;
				}
			}
			
			
			
			int k = l;
			
			
			
			
			/*for(int b = (N+1)/2; b >= 1; b /= 2){ 
				while(b + k < N && skim(b + k + 1) < A) k += b;
			}*/
			for(int i = k; i >= 10 && k - i < 10; i --){
				v.pb({skim(i+1), i});
			} 
			
			if(k + 1 < N){
				v.pb({skim(k+2), k+1});
			}
			iter(A, K);
		}
		else{
			if(S == 1 && pref[0] <= 2*A){
				answer({1});
			}
			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