Submission #406254

#	Time	Username	Problem	Language	Result	Execution time	Memory
406254		jamezzz	A Difficult(y) Choice (BOI21_books)	C++14	50 / 100	211 ms	7344 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();
		for(int i=N-K+1;i<=N;++i){
			if(a[i]==-1)a[i]=skim(i);
		}
		int tmp;
		for(int i=K;i>=1;--i){
			if(!use[N-K+i]&&sm-a[i]+a[N-K+i]<=2*A){
				use[i]=false;
				use[N-K+i]=true;
				sm=sm-a[i]+a[N-K+i];
			}
			else{
				tmp=i;break;
			}
		}
		if(A<=sm){
			vector<int> v;
			for(int i=1;i<=N;++i){
				if(use[i])v.push_back(i);
			}
			answer(v);
		}
		else{
			for(int i=1;i<=N;++i){
				if(!use[i])s.insert(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[tmp]&&sm+a[val]-a[tmp]<=2*A){
					res=val;break;
				}
				else if(sm+a[val]-a[tmp]<A){
					lo=mid+1;
					res=val;
				}
				else hi=mid-1;
			}
			if(res!=0){
				s.erase(res);
				s.insert(tmp);
				sm+=a[res]-a[tmp];
			}
			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();
		}
	}
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:96:21: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     sm+=a[res]-a[tmp];
      |                ~~~~~^

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