Submission #1123084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123084		thelegendary08	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	1180 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#define ll long long int
#define vi vector<long long int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)

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.
//

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    vi v(N, -1);
    ll s = 0;
	f0r(i, K - 1){
		if(v[i] == -1)v[i] = skim(i + 1);
		s += v[i];
	}
	int lo = 0;
	int hi = N;
	while(lo < hi){
		int mid = lo + (hi - lo)/2;
		if(v[mid] == -1)v[mid] = skim(mid + 1);
		if(v[mid] > A){
			hi = mid;
		}
		else lo = mid + 1;
	}
	if(lo != N && s + v[lo] >= A && s + v[lo] <= 2 * A){
		vector<int> ans;
		f0r(i, K-1)ans.pb(i + 1);
		ans.pb(lo + 1);
		answer(ans);
	}
	else{
		//cout<<lo<<'\n';
		//solve from 0 to lo-1
		if(lo < K)impossible();
		else{
			if(v[K-1] == -1)v[K-1] = skim(K);
			for(int i = lo - 1; i>=lo - K; i--){
				if(v[i] == -1)v[i] = skim(i + 1);
			}
			/*
			vi w;
			f0r(i, K)w.pb(v[i]);
			for(int i = lo - 1; i>=lo - K; i--){
				w.pb(v[i]);
			}
			*/
			f0r(i, K+1){
				ll cur = 0;
				vector<int>ans;
				f0r(j, i){
					cur += v[j];
					//cout<<v[j]<<' ';
					ans.pb(j + 1);
				}
				int cnt = K - i;
				for(int j = lo - 1; j>= lo - cnt; j--){
					cur += v[j];
					ans.pb(j + 1);
				}
				
				if(cur >= A && cur <= 2 * A){
					answer(ans);
				}
			}
			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