Submission #530603

#	Time	Username	Problem	Language	Result	Execution time	Memory
530603		huangqr	A Difficult(y) Choice (BOI21_books)	C++14	20 / 100	245 ms	968 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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.
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    vector<ll>a(N+1,0);
	vector<int>ret;
	ll cur=0;
    for(int i=1;i<=N;i++)a[i]=skim(i);
    for(int i=1;i<=K;i++){
    	cur+=a[i];
	}
	if(cur >= A && cur <= 2*A){
		for(int i=1;i<=K;i++)ret.push_back(i);
		answer(ret);
	}
	ll bound = N+1;
	for(int i=K;i>=1;i--){
		cur -= a[i];
		if(bound <= i+1)impossible();
		auto pos = upper_bound(a.begin()+i+1,a.begin()+bound,2*A-cur);
		if(pos==a.begin()+i+1)impossible();
		pos--;
		bound = pos - a.begin();
		cur += a[bound];
		ret.push_back(bound);
		if(cur >= A && cur <= 2*A){
			for(int j=1;j<=i-1;j++)ret.push_back(j);
			answer(ret);
		}
	}
    impossible();
}

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