Submission #659716

#	Time	Username	Problem	Language	Result	Execution time	Memory
659716		radal	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	452 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
 
typedef long long ll;
constexpr int N = 1e6+15,mod = 1e9+7,inf = 1e9+10,sq = 620,maxm = 2e6+10;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
 
ll a[N];
 
void solve(int n, int k, long long A, int s) {
    // TODO implement this function
	ll sum = 0;
	rep(i,1,k+1){
 		a[i] = skim(i);
		sum += a[i];
	}
	if (sum > 2*A){
		impossible();
		return;
	}
	vector<int> ans;
	if (sum >= A){
		rep(i,1,k+1) ans.pb(i);
		answer(ans);
		return;
	}
	int l = 0,r = n+1,m;
	while (r-l > 1){
		m = (l+r) >> 1;
		a[m] = skim(m);
		if (a[m] >= A) r = m;
		else l = m;
	}
	if (r != n+1 && a[r]-a[k]+sum <= 2*A){
		rep(i,1,k) ans.pb(i);
		ans.pb(r);
		answer(ans);
		return;
	}
	ll sum2 = 0;
	rep(i,r-k,r){
		a[i] = skim(i);
		sum2 += a[i];
	}
	if (sum2 < A){
		impossible();
		return;
	}
	int po = 1,po2 = r-k;
	while (sum2 > 2*A){
		sum2 -= a[po2];
		sum2 += a[po];
		po2++;
		po++;
	}
	rep(i,1,po) ans.pb(i);
	rep(i,po2,r) ans.pb(i);
	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