Submission #573944

#	Time	Username	Problem	Language	Result	Execution time	Memory
573944		moday_morning	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	2 ms	336 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) {
	int l = 0, r = N - K + 1; 
	long long left = 2 * A / K, rr = (A + K - 1) / K;
	while (l <= r) {
		int mid = (l + r) / 2;
		long long check = all(1, mid), check2 = all(1, mid + K - 1);
		if (left < check) {
			r = mid - 1;
		}
		else if (rr > check2) {
			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: 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