Submission #1123024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123024		thelegendary08	A Difficult(y) Choice (BOI21_books)	C++20	25 / 100	2 ms	1196 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);
    int lo = 0;
    int hi = N - K;
    while(lo < hi){
    	int mid = lo + (hi - lo)/2;
    	ll cur = 0;
    	for(int i = mid; i<mid + K; i++){
    		if(v[i] == -1){
    			v[i] = skim(i+1);
    		}
    		cur += v[i];
    	}
    	if(cur >= A){
    		hi = mid;
    	}
    	else lo = mid + 1;
    }
    for(int i = lo; i<lo+K; i++){
    	if(v[i] == -1)v[i] = skim(i + 1);
    }
    if(lo == 0){
    	ll cur = 0;
    	f0r(i, K){
    		if(v[i] == -1)v[i] = skim(i + 1);
    		cur += v[i];
    	}
    	if(cur > 2 * A)impossible();
    	else{
    		vector<int> ans;
    		f0r(i, K)ans.pb(i + 1);
    		answer(ans);
    	}
    }
    else{
    	if(v[lo-1] == -1){
    		v[lo-1] = skim(lo);
    	}
    	bool ok = 0;
    	ll sum = 0;
    	for(int i = lo-1; i<=lo + K - 1; i++){
    		sum += v[i];
    	}
    	for(int i = lo-1; i<=lo + K - 1; i++){
    		if(sum - v[i] >= A && sum - v[i] <= 2 * A){
    			vector<int> ans;
    			for(int j = lo-1; j<=lo + K - 1; j++){
    				if(j != i)ans.pb(j+1);
    			}
    			ok = 1;
    			answer(ans);
    			break;
    		}
    	}
    	if(!ok){
    		int s = 0;
    		f0r(i, K - 1){
    			if(v[i] == -1)v[i] = skim(i + 1);
    			s += v[i];
    		}
    		int lo = 0;
    		int hi = K;
    		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 == K)impossible();
    		else if(s + v[lo] <= 2 * A){
    			vector<int> ans;
    			f0r(i, K-1)ans.pb(i + 1);
    			ans.pb(lo + 1);
    			answer(ans);
    		}
    		else impossible();
    	}
    }
    
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20