Submission #1166577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166577		ByeWorld	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	408 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;

ll n, query, num;
ll a;
vector <int> ans;
set <int> s; 
void out(){
	vector <int> ret;
	for(auto in : s) ret.pb(in);
	answer(ret);
}
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;

	for(int i=1; i<=num-1; i++) que(i);
	int l=num, r=n, mid=0, cnt=-1;
	while(l<=r){
		mid = md;
		if(que(mid) > a){
			cnt = mid; r = mid-1;
		} else l = mid+1;
	}
	// cout << cnt << " cnt\n";
	if(cnt != -1){
		vector <int> ans;
		ll tot = que(cnt);
		for(int i=1; i<=num-1; i++) tot += que(i), ans.pb(i);
		ans.pb(cnt);
		if(a<=tot && tot<=2*a) answer(ans);
	}

	if(cnt==-1) cnt = n;
	else cnt--;
	if(cnt <= 2*num){
		for(int i=1; i<=cnt; i++) que(i);

		for(int i=1; i<=cnt-num+2; i++){
			ll tot = 0;
			for(int j=i; j<=i+num-2; j++){
				tot += que(j); s.insert(j);
			}
			for(int j=1; j<=i-1; j++){
				tot += que(j); s.insert(j);
				if(a<=tot && tot<=2*a) out();
				tot -= que(j); s.erase(j);
			}
			for(int j=i+num-1; j<=cnt; j++){
				tot += que(j); s.insert(j);
				if(a<=tot && tot<=2*a) out();
				tot -= que(j); s.erase(j);
			}
		}
	} else {
		for(int i=1; i<=num; i++) que(i);
		for(int i=cnt; i>=cnt-num+1; i--) que(i);

		ll tot = 0; 
		for(int i=1; i<=num; i++){ tot += que(i); s.insert(i); }
		if(a<=tot && tot<=2*a) out();
		for(int i=1; i<=num; i++){
			tot -= que(i); s.erase(i);
			tot += que(cnt-num+i); s.insert(cnt-num+i);
			if(a<=tot && tot<=2*a) out();
		}
	}
	

	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: 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