Submission #656834

#	Time	Username	Problem	Language	Result	Execution time	Memory
656834		ktkerem	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	336 KiB

books

#include<bits/stdc++.h>
#include "books.h"
typedef long long ll;
typedef std::pair<ll , ll> llll;
typedef std::string str;
#define debug std::cout << "debug" << std::endl
#define pb push_back
ll kp[150000];
ll fun(ll x){
	if(kp[x] == 0){
		kp[x] = skim(x);
	}
	return kp[x];
}
void solve(int n , int m ,ll a , int s){
	ll tot = 0;
	for(ll i = 1;m>i;i++){
		tot+=fun(i);
	}
	ll l = m , r = n+1;
	while(r - l > 1){
		ll md = (l+r)/2;
		if(fun(md) + tot > 2ll *a){
			r = md;
		}
		else{
			l = md;
		}
	}
	if(tot + fun(l) > 2ll *a){
		impossible();
		return;
	}
	if(tot + fun(l) >= a && 2ll *a >= tot + fun(l)){
		std::vector<int> v;
		for(ll i = 1;m>i;i++){
			v.pb(i);
		}
		v.pb(l);
		answer(v);
		return;
	}
	for(ll i = m;i >= 0;i--){
		ll ss = 0;
		for(ll j =1;i>=j;j++){
			ss+=fun(j);
		}
		for(ll j = 1;m - i>=j;j++){
			ss+=fun(l - j + 1);
		}
		if(ss >= a && 2ll *a >= ss){
			std::vector<int> v;
			for(ll j =1;i>=j;j++){
				v.pb(j);
			}
			for(ll j = 1;m - i>=j;j++){
				v.pb(l - j + 1);
			}
			answer(v);
			return;
		}
		tot = 0;
	}
	impossible();
}
/*int main(){
	#ifndef ONLINE_JUDGE
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	ll t = 1;std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}*/

• 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