Submission #549860

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

books

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

ll arr[25],a,chk=0,diff[100005];
vector<pair<ll,int> > V;

void gen(ll lv, ll til, ll k){
	if(lv == til){
		ll cnt = 0, val = 0;
		for(int i=0;i<til;i++){
			cnt += arr[i];
			if(arr[i]) val += V[i].first;
//			printf("%d ",arr[i]);
		}
//		printf(" : %d %d %d %d\n",cnt,val,k,a);
		if(cnt == k && val >= a && val <= 2*a && !chk){
			vector<int> ANS;
			for(int i=0;i<til;i++) if(arr[i]) ANS.push_back(V[i].second);
			answer(ANS);
			chk = 1;	
		}
		return;
	}
	
	arr[lv] = 0;
	gen(lv+1,til,k);
	arr[lv] = 1;
	gen(lv+1,til,k);
}

void solve(int n, int k, long long A, int s){
	ll be = 1,ed = n;
	a = A;
    while(be <= ed){
        ll mid = (be+ed)/2,val;
        diff[mid] = skim(mid);
		if(diff[mid] > a) ed = mid-1;
		else be = mid+1;		
    }
    if(ed != n) ed++;
//    printf("ed = %d %d\n",ed,a);
    if(ed < k){
		impossible();
		return;
	}
	for(int i=1;i<=k;i++){
		if(!diff[i]) diff[i] = skim(i);
		V.push_back({diff[i],i});
	}
	for(int i=max((ll)k+1,ed-k+1);i<=ed;i++){
		if(!diff[i]) diff[i] = skim(i);
		V.push_back({diff[i],i});
	}
    
    gen(0,V.size(),k);
    
    if(!chk) impossible();
}

/*
8 3 33 8
1 32 33 56 67 78 89 100

8 3 3 8
1 2 3 4 5 6 7 8
*/

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:37:28: warning: unused variable 'val' [-Wunused-variable]
   37 |         ll mid = (be+ed)/2,val;
      |                            ^~~

• 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