Submission #551887

#	Time	Username	Problem	Language	Result	Execution time	Memory
551887		keta_tsimakuridze	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	1096 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> get(int L, int R) {
	vector<int> v;
	for(int i = L; i <= R; i++) v.push_back(i + 1);
	return v;
}
void solve(int N, int K, long long A, int S) {
	#define ll long long
    ll l = 0, r = N - 1, x = N, val = 0 ;
	while(l <= r) {
		ll mid = (l + r) / 2;
		ll a = skim(mid + 1);
		if(a >= A) x = mid, val = a, r = mid - 1;
		else l = mid + 1;
	} 
	vector<ll> a(N);
	for(ll i = 0; i < K; i++) a[i] = skim(i + 1);
	for(ll i = x - 1; i >= max(0ll, x - K); i--) a[i] = skim(i + 1);
	ll sum0 = 0;
	for(ll i = 0; i < K; i++) {
		sum0 += a[i];
	}
	if(sum0 > 2 * A)  {
		impossible();
		return;
	}
	vector<int> all;
	for(ll i = 0; i < N; i++) {
		if(i < K || (i >= max(0ll, x - K) && i < x)) all.push_back(i);
	}
	if(sum0 >= A) {
		answer(get(0, K - 1));
		return ;
	}
	if(x < N && val + sum0 - a[K - 1] <= 2 * A) {
		vector<int> v = get(0, K - 2);
		v.push_back(x + 1);
		answer(v);
		return;
	}
	for(ll i = K; i < all.size(); i++) {
		sum0 += a[all[i]] - a[all[i - K]];
		if(sum0 >= A && sum0 <= 2 * A) {
			vector<int> v;
			for(ll j = i - K + 1; j <= i; j++) {
				v.push_back(all[j] + 1);
			}
			answer(v);
			return;
		}		
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(ll i = K; i < all.size(); i++) {
      |                ~~^~~~~~~~~~~~

• 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