Submission #1130170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130170		ByeWorld	A Difficult(y) Choice (BOI21_books)	C++20	25 / 100	1 ms	412 KiB

books

#include <bits/stdc++.h>

#include "books.h"

#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<char,char> pcc;
typedef pair<ll,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+20;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 32;
const ld EPS = 1e-12;

int n, query, num;
ll a;
vector <int> ans;
map<ll,ll> m;

ll que(int x){
	if(m.find(x) == m.end()){
		m[x] = skim(x); 
	}
	return m[x];
}
void solve(int N, int K, long long A, int S) {
	n = N, num = K, a = A; query = S;

	int l=num, r=n, mid=0, cnt=-1;
	while(l<=r){
		mid = md;
		if(que(mid)*num < a){ l = mid+1; continue; }
		if(2*a < que(mid-num+1)*num){ r = mid-1; continue; }
		// mid-num+1  -- mid
		ll te = 0;
		for(int i=mid-num+1; i<=mid; i++) te += que(i);

		if(a<=te && te<=2*a){
			for(int i=mid-num+1; i<=mid; i++) ans.pb(i);
			answer(ans);
		}

		if(te < a){ l = mid+1; cnt = mid; }
		else r = mid-1;
	}
	if(cnt == -1){ // gk ada yg < a
		ll te = 0;
		for(int i=1; i<=num; i++) te += que(i);
		if(2*a < te) impossible();

		for(int i=1; i<=num; i++) ans.pb(i);
		answer(ans);
	}

	l=cnt+1, r=n, mid=0;
	ll te = 0;
	for(int i=cnt-num+1; i<=cnt-1; i++) ans.pb(i);
	for(int i=cnt-num+1; i<=cnt-1; i++) te += que(i);
	while(l<=r){
		mid = md;
		if(a<=te+que(mid) && te+que(mid)<=2*a){
			ans.pb(mid);
			answer(ans);
		}
		if(te+que(mid) < a) l = mid+1;
		else r = mid-1;
	}

	l=1, r=cnt-1, mid=0;
	while(l<=r){
		mid = md;
		if(a<=te+que(mid) && te+que(mid)<=2*a){
			ans.pb(mid);
			answer(ans);
		}
		if(te+que(mid) < a) l = mid+1;
		else r = mid-1;
	}
	impossible();
}

Compilation message (stderr)

books.cpp:20:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 | const int INF = 1e18+10;
      |                 ~~~~^~~

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