| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 398865 | couplefire | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int n, int k, long long goal, int s){
// binary search for first pos >= goal
int lo = 0, hi = n-1, pos;
while(lo < hi){
int mid = lo+(hi-lo)/2;
long long val = skim(mid+1);
if(val >= goal) hi = mid;
else lo = mid+1;
}
pos = lo; long long val = skim(pos);
if(val < goal) pos = n;
vector<long long> ans;
if(pos < k-1){
impossible();
return;
}
if(pos != n){
long long sum = 0;
for(int i = 0; i<k-1; i++) sum += skim(i+1);
if(goal <= sum+val && sum+val <= 2*goal){
for(int i = 0; i<k-1; i++) ans.push_back(i+1);
ans.push_back(pos+1);
answer(ans);
return;
}
if(pos == k-1){
impossible();
return;
}
}
vector<int> arr(n);
for(int i = 0; i<k; i++) arr[i] = skim(i+1);
for(int i = pos-1; i>=pos-k; i--) arr[i] = skim(i+1);
for(int i = 0; i<=k; i++){
long long sum = 0;
for(int j = 0; j<i; j++) sum += arr[j];
for(int j = pos-1; j>=pos-(k-i); j--) sum += arr[j];
if(goal <= sum && sum <= 2*goal){
for(int j = 0; j<i; j++) ans.push_back(j+1);
for(int j = pos-1; j>=pos-(k-i); j--) ans.push_back(j+1);
answer(ans);
return;
}
}
impossible();
}