Submission #573808

#	Time	Username	Problem	Language	Result	Execution time	Memory
573808		moday_morning	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	1 ms	292 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

map <int, long long> mp;
long long all(int k, int p) {
	long long sum = 0;
	for (int i = 0; i < k; i++) {
		int pos = i + 1 + p;
		if (mp.find(pos) == mp.end()) {
			mp[pos] = skim(pos);
			sum += mp[pos]; 
		}
	}
	return sum;
}

void solve(int N, int K, long long A, int S) {
	long long l = 0, r = N - K + 1, left = 2 * A / K, rr = (A + K - 1) / K;
	while (l <= r) {
		long long mid = (l + r) / 2, lll = all(1, mid), rrr = all(1, mid + K - 1);
		if (left < lll) {
			r = mid;
		}
		else if (rr > rrr) {
			l = mid + 1;
		}
		else {
			if (A * 2 < all(K, mid)) {
				r = mid - 1;
			}
			else if (A > all(K, mid)) {
				l = mid + 1;
			}
			else {
				vector <int> st;
				for (int i = 0; i < K; i++) {
					int pos = mid + i + 1;
					st.push_back(pos);
				}
				answer(st);
				return;
			}
		}
	}
	l = K;
	r = N - 1;
	while (l <= r) {
		int mid = (l + r) / 2;
		long long check = all(K - 1, 0) + all(1, mid);
		if (A * 2 < check) {
			r = mid - 1;
		}
		else if (A > check) {
			l = mid + 1;
		}
		else {
			vector <int> st;
			for (int i = 0; i < K - 1; i++) {
				int pos = i + 1;
				st.push_back(pos);
			}
			st.push_back(mid + 1);
			answer(st);
			return;
		}
	}
	impossible();
}

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