Submission #724712

#	Time	Username	Problem	Language	Result	Execution time	Memory
724712		gagik_2007	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	248 ms	1080 KiB

books

#include "books.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll NNN = 100007;
ll n, k, a, s;
ll p[100007];

void ansfrom(ll st) {
	vector<int>v;
	for (ll i = st; i < st + k; i++) {
		v.push_back(i + 1);
	}
	answer(v);
	exit(0);
}

void check(ll sum, ll st) {
	if (sum >= a && sum <= 2 * a)ansfrom(st);
}

ll skimm(ll ind) {
	if (p[ind] != -1)return p[ind];
	return p[ind] = skim(ind);
}

ll sum_from(ll ind) {
	ll res = 0;
	for (ll i = ind; i < ind + k; i++) {
		res += skimm(i);
	}
	return res;
}

void solve(int N, int K, ll A, int S) {
	n = N;
	k = K;
	a = A;
	s = S;
	if (n == s) {
		ll sum = 0;
		ll least = -1;
		for (ll i = 0; i < n; i++) {
			p[i] = skim(i + 1);
			if (i < k - 1)sum += p[i];
			else if (p[i] > a && least == -1)least = i;
		}
		if (least != -1 && sum + p[least] >= a && sum + p[least] <= 2 * a) {
			vector<int>v;
			for (ll i = 0; i < k - 1; i++) {
				v.push_back(i + 1);
			}
			v.push_back(least + 1);
			answer(v);
			return;
		}
		else {
			sum += p[k - 1];
			check(sum, 0);
			for (ll i = k; i < n; i++) {
				sum -= p[i - k];
				sum += p[i];
				check(sum, i - k + 1);
			}
			impossible();
			return;
		}
	}
	else {
		ll sum = 0;
		vector<int>v;
		for (ll i = 1; i <= n; i++) {
			p[i] = -1;
		}
		for (ll i = 0; i < k - 1; i++) {
			sum += skimm(i + 1);
			v.push_back(i + 1);
		}
		if (sum + skimm(k) > 2 * a) {
			impossible();
			return;
		}
		ll l = k, r = n + 1;
		while (l < r) {
			ll m = (l + r) / 2;
			if (skimm(m) >= a) {
				r = m;
			}
			else {
				l = m + 1;
			}
		}
		int ind = l;
		//cout << "ind: " << ind << endl;
		if (ind <= n) {
			ll val = sum + skimm(l);
			if (val >= a && val <= 2 * a) {
				v.push_back(l);
				answer(v);
				return;
			}
		}
		if (2 * k >= ind) {
			l = 1, r = ind - k + 1;
			while (l < r) {
				ll mid = (l + r) / 2;
				sum = sum_from(mid);
				//cout << mid << ": " << sum << ": " << sum - a << endl;
				if (a <= sum && sum <= 2 * a) {
					ansfrom(mid - 1);
				}
				else if (a > sum) {
					l = mid + 1;
				}
				else {
					r = mid;
				}
			}
			sum = sum_from(l);
			//cout << l << ": " << sum << ": " << sum - a << endl;
			if (a <= sum && sum <= 2 * a) {
				ansfrom(l - 1);
			}
			impossible();
			return;
		}
		else {
			sum = 0;
			for (int i = 1; i <= k; i++) {
				sum += skimm(i);
			}
			//cout << "sum: " << sum << endl;
			int i = 1;
			int j = ind - k;
			if (a <= sum && sum <= 2 * a) {
				v.clear();
				for (int p = i; p <= k; p++) {
					v.push_back(p);
				}
				for (int p = ind - k; p < j; p++) {
					v.push_back(p);
				}
				answer(v);
				return;
			}
			while (j < ind) {
				sum -= skimm(i);
				i++;
				sum += skimm(j);
				j++;
				//cout << "sum: " << sum << endl;
				//cout << i << " " << j << endl;
				if (a <= sum && sum <= 2 * a) {
					v.clear();
					for (int p = i; p <= k; p++) {
						v.push_back(p);
					}
					for (int p = ind - k; p < j; p++) {
						v.push_back(p);
					}
					answer(v);
					return;
				}
			}
			impossible();
			return;
		}
	}
}

• 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