Submission #724690

#	Time	Username	Problem	Language	Result	Execution time	Memory
724690		gagik_2007	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	240 ms	1040 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 if (s >= 170) {
		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;
		while (l < r) {
			ll m = (l + r) / 2;
			if (skimm(m) >= a) {
				r = m;
			}
			else {
				l = m + 1;
			}
		}
		int ind = l;
		ll val = sum + skimm(l);
		if (val >= a && val <= 2 * a) {
			v.push_back(l);
			answer(v);
			return;
		}
		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;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20