제출 #405967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405967		jamezzz	A Difficult(y) Choice (BOI21_books)	C++14	30 / 100	271 ms	7384 KiB

books

#include <bits/stdc++.h>
using namespace std;

#include "books.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef long long ll;
//less_equal for identical elements
//
// --- 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 a[100005];
bool use[100005];
pbds s;

void solve(int N, int K, long long A, int S) {
    if(N==S&&K==3){
		for(int i=1;i<=N;++i)a[i]=skim(i);
		for(int i=1;i<=N;++i){
			for(int j=i+1;j<=N;++j){
				for(int k=j+1;k<=N;++k){
					if(A<=a[i]+a[j]+a[k]&&a[i]+a[j]+a[k]<=2*A){
						answer({i,j,k});
						return;
					}
				}
			}
		}
		impossible();
	}
	else{
		memset(a,-1,sizeof a);
		ll sm=0;
		for(int i=1;i<=K;++i){
			a[i]=skim(i);
			sm+=a[i];
			use[i]=true;
		}
		if(2*A<sm)impossible();
		else{
			for(int i=K+1;i<=N;++i)s.insert(i);
			for(int i=1;i<=K;++i){
				int lo=1,hi=s.size(),mid,res=0;
				while(lo<=hi){
					mid=(lo+hi)/2;
					int val=*s.find_by_order(mid-1);
					if(a[val]==-1)a[val]=skim(val);
					if(A<=sm+a[val]-a[i]&&sm+a[val]-a[i]<=2*A){
						res=val;break;
					}
					else if(sm+a[val]-a[i]<A){
						lo=mid+1;
						res=val;
					}
					else hi=mid-1;
				}
				if(res!=0){
					s.erase(res);
					s.insert(i);
					sm+=a[res]-a[i];
				}
				if(A<=sm&&sm<=2*A){
					vector<int> ans;
					for(int i=1;i<=N;++i){
						if(s.find(i)==s.end())ans.push_back(i);
					}
					answer(ans);
					return;
				}
			}
			impossible();
		}
	}
}

• Subtask 1: 5 / 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