Submission #697801

#	Time	Username	Problem	Language	Result	Execution time	Memory
697801		Sandarach151	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	304 KiB

books

#include <bits/stdc++.h> 
#include "books.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
using namespace std;
 
ll n,k,a,s;
 
map<int,ll> memo;
 
ll ask(int i){
	if (memo.count(i)) return memo[i];
	else return memo[i]=skim(i);
}
 
void solve(int N, int K, long long A, int S) {
	n=N,k=K,a=A,s=S;
	
    ll tot=0;
    
    vector<int> ans;
    rep(x,1,k+1){
		tot+=ask(x);
		ans.pub(x);
	}
	
    if (a<=tot && tot<=2*a){
		answer(ans);
		return;
	}
	if (2*a<tot){
		impossible();
		return;
	}
	
	int lo=1,hi=n+1,mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (ask(mi)<=a) lo=mi;
		else hi=mi;
	}
	
	if (lo!=n){
		ll temp=tot-ask(k)+ask(lo+1);
		if (a<=temp && temp<=2*a){
			ans.back()=lo+1;
			answer(ans);
			return;
		}
	}
	
	rep(x,0,k){
		ans[k-1-x]=lo-x;
		tot-=ask(k-x);
		tot+=ask(lo-x);
		
		//cout<<tot<<endl;
		
		if (tot<a) continue;
		if (tot<=2*a){
			answer(ans);
			return;
		}
	}
	
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:55:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   mi=hi+lo>>1;
      |      ~~^~~

• 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