Submission #424827

#	Time	Username	Problem	Language	Result	Execution time	Memory
424827		patrikpavic2	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	392 KiB

books

#include "books.h"

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef long long ll;

ll A[(int)(1e5 + 500)];
vi v;

ll pitaj(int x){
	if(A[x]) return A[x];
	A[x] = skim(x + 1);
	v.PB(x);
	return A[x];
}

bool cmp(int i, int j){
	return A[i] < A[j];
}

vi nadi(int n, int k, ll L){
	sort(v.begin(), v.end(), cmp); vi ret;
	for(int i = 0;i + k <= (int)v.size();i++){
		ll cur = 0;
		for(int j = 0;j < k;j++)
			cur += A[v[i + j]];
		if(L <= cur && cur <= 2LL * L){
			for(int j = 0;j < k;j++)
				ret.PB(v[i + j]);
			return ret;
		}
	}
	for(;(int)v.size() >= k;v.pop_back()){
		for(int i = 0;i <= k;i++){
			ll cur = 0;
			for(int j = 0;j < i;j++)
				cur += A[v[j]];
			for(int j = 0;j < k - i;j++)
				cur += A[v[(int)v.size() - j - 1]];
			if(L <= cur && cur <= 2LL * L){
				for(int j = 0;j < i;j++)
					ret.PB(v[j]);
				for(int j = 0;j < k - i;j++)
					ret.PB(v[(int)v.size() - j - 1]);
				return ret;
			}
		}
	}
	return ret;
}

void solve(int n, int k, ll L, int S) {
	//printf("n = %d k = %d L = %lld S = %d\n", n, k, L, S);
	int pref = -1;
	for(int i = 18;i >= 0;i--){
		if(pref + (1 << i) < n && pitaj(pref + (1 << i)) <= L)
			pref += (1 << i);
	}  
	pref++; if(pref < n) pitaj(pref);
	for(int i = 0;i < k;i++) 
		pitaj(i);
	//printf("tu sam pref = %d\n", pref);
	for(int i = 0;i < k && pref - i - 1 >= 0;i++) 
		pitaj(pref - i - 1);
	vi ans = nadi(n, k, L);
	if((int)ans.size() == 0)
		impossible();
	for(int &x : ans) x++;
	answer(ans);
}

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