Submission #557889

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

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll T[LIM];
ll pytaj(int x) {
	if(!T[x]) T[x]=skim(x);
	return T[x];
}
void solve(int n, int k, ll A, int S) {
	int l=1, r=n;
	while(l<r) {
		int sr=(l+r+1)/2;
		if(pytaj(sr)*k<=2*A) l=sr; else r=sr-1;
	}
	if(pytaj(l)*k>2*A) {
		impossible();
		return;
	}
	vector<pair<ll,int>>V;
	for(int i=max(l-k+1, 1); i<=min(l+k, n); ++i) {
		V.pb({pytaj(i), i});
		if(V.back().st>=A) break;
	}
	bool t=false;
	for(int i=0; i+k<=V.size(); ++i) {
		ll sum=0;
		rep(j, k) sum+=V[i+j].st;
		if(sum>=A) {
			if(sum<=2*A) {
				vector<int>ans;
				rep(j, k) ans.pb(V[i+j].nd);
				answer(ans);
				return;
			} else {
				if(V.back().nd>=k) t=true;
				break;
			}
		}
	}
	if(t) {
		ll sum=V.back().st;
		rep(i, k-1) sum+=pytaj(i+1);
		if(A<=sum && sum<=2*A) {
			vector<int>ans;
			rep(i, k-1) ans.pb(i+1);
			ans.pb(V.back().nd);
			answer(ans);
			return;
		}
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0; i+k<=V.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