Submission #411866

#	Time	Username	Problem	Language	Result	Execution time	Memory
411866		Bill_00	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	300 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#define ll long long
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.
//
long long x[100005];
// long long skim(int a){
// 	return a;
// }
// void answer(vector<int>k){
// 	return;
// }
// void impossible(){
// 	return;
// }
void solve(int N, int K, long long A, int S) {
   vector<int>ans;
   ll sum=0,p=0;
   for(int i=1;i<=K;i++){
   	x[i]=skim(i);
   	sum+=x[i];
   }
   if(sum>2*A) impossible();
   if(sum>=A){
   	for(int i=1;i<=K;i++){
   		ans.push_back(i);
   	}
   	answer(ans);
   }
   int l=1,r=N;
   while(l<r){
   	int m=(l+r+1)>>1;
   	long long y=skim(m);
   	if(x[1]+A>=y){
   		l=m;
   	}
   	else r=m-1;
   }
   for(int i=max(l-K+1,1);i<=l;i++){
   	x[i]=skim(i);
   	p+=x[i];
   }
   if(l==N && p<A) impossible();
   if(p<A){
   	if(sum-x[K]+skim(l+1)>2*A) impossible();
   	else{
   		for(int i=1;i<K;i++){
   			ans.push_back(i);
   		}
   		ans.push_back(l+1);
   	}
   }
   for(int i=1;i<=K;i++){
   	ans.clear();
   	ll s=0;
   	for(int j=1;j<=i;j++){
   		s+=x[j];
   		ans.push_back(j);
   	}
   	for(int j=l;j>l-K+i;j--){
   		s+=x[j];
   		ans.push_back(j);
   	}
   	if(s>=A && s<=2*A) answer(ans);
   }



}
// int main(){
// 	solve(5,5,10,2);
// }

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