Submission #724611

#	Time	Username	Problem	Language	Result	Execution time	Memory
724611		gagik_2007	A Difficult(y) Choice (BOI21_books)	C++17	20 / 100	227 ms	1068 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(int st) {
	vector<int>v;
	for (int i = st; i < st + k; i++) {
		v.push_back(i + 1);
	}
	answer(v);
	exit(0);
}

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

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

void solve(int N, int K, long long A, int S) {
	n = N;
	k = K;
	a = A;
	s = S;
	if (n == s) {
		ll sum = 0;
		ll least = -1;
		for (int 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 (int 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 (int 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 (int i = 1; i <= n; i++) {
			p[i] = -1;
		}
		for (int i = 0; i < k - 1; i++) {
			sum += skimm(i + 1);
			v.push_back(i + 1);
		}
		if (sum + skimm(k) > 2 * a || sum + skimm(n) < a) {
			impossible();
			return;
		}
		int l = k, r = n;
		while (l < r) {
			int m = (l + r) / 2;
			ll val = sum + skimm(m);
			if (val >= a && val <= 2 * a) {
				v.push_back(m);
				answer(v);
				return;
			}
			else if (val < a) {
				l = m + 1;
			}
			else {
				r = m;
			}
		}
		ll val = sum + skimm(l);
		if (val >= a && val <= 2 * a) {
			v.push_back(l);
			answer(v);
			return;
		}
		impossible();
		return;
	}
}

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