| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1354152 | nataliaa | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
void answer(vector<int> v)
{
printf("answer({");
for(int i = 0; i < (int) v.size(); ++i)
{
printf("%d", v[i]);
if(i + 1 != (int) v.size()) printf(", ");
}
printf("})\n");
if ((int) v.size() != K) result("Invalid answer");
ll sum = 0;
for(auto x: v) {
if (x<1 || x>N) result("Invalid answer");
sum += seq[x];
}
if (sum < A || 2*A<sum) result("Wrong answer");
result("Correct: %d book(s) skimmed", sUsed);
exit(0);
}
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int n, int k, long long a, int Q) {
int l = 1, r = n;
vector<int> ans;
int es = n+1;
while(l<=r){
int m = (l+r)/2;
long long ok = skim(m);
if(ok>a) {r = m-1; es = m;}
else if(ok<a) {l = m+1;}
else {
es= m;
break;
}
}
//cout << es <<endl;
vector<pair<int,int>> v;
long long s = 0;
for(int i = 1; i<= k; i++) {
long long x = skim(i);
s+=x;
v.push_back({x, i});
}
if(s>2*a) {impossible(); return;}
int q = es-k;
q = max(1, q);
if(es-k<=k) q = k+1;
for(int i = q; i< es; i++){
long long x = skim(i);
v.push_back({x, i});
}
int sum1 = s - v[k-1].first;
if(es!=n+1) sum1+=skim(es);
if(sum1>=a&&sum1<=2*a&&es!=n+1){
for(int i = 1; i< k; i++) ans.push_back(i);
ans.push_back(es);
answer(ans);
return;
}
//cout << s << endl;
int m = v.size();
r = k-1, l = 0;
while(r<m-1){
if(s>=a&&s<=2*a){
for(int i = l; i<=r; i++) ans.push_back(v[i].second);
answer(ans); return;
}
s-=v[l].first;
r++;
l++;
s+=v[r].first;
}
if(s>=a&&s<=2*a){
for(int i = l; i<=r; i++) ans.push_back(v[i].second);
answer(ans); return;
}
impossible();
}