Submission #401009

#	Time	Username	Problem	Language	Result	Execution time	Memory
401009		errorgorn	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	296 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;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

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:65:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   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