| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1354118 | takoshanava | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "books.h"
//#define int long long
#define ll long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
void solve(int n, int k, long long a, int s){
vector<pair<int, int>> vec;
ll sum = 0;
for(int i = 1; i <= k; i++){
int v = skim(i); vec.pb({v, i}), sum += v;
}
for(int i = max(k + 1, n - k + 1); i <= n; i++) vec.pb({skim(i), i});
if(sum > 2 * a) impossible();
int r = k, l = 1;
vector<int> res;
while(r < n){
sum -= vec[l].fs;
r++;
sum += vec[r].fs;
if(sum >= a and sum <= 2 * a){
for(int i = l; i <= r; i++) res.pb(vec[i].sc);
answer(res);
}
l++;
}
if(sum < a) impossible();
int val = 1e18;
l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
int v = skim(mid);
if(v > a) r = mid - 1;
else l = mid + 1, val = v;
}
vector<pair<int, int>> vec1;
for(int i = 0; i < k; i++) vec1.pb({vec[i].fs, i});
for(int i = max(k + 1, l - k); i < l; i++) vec1.pb({skim(i), i});
r = k, l = 1;
while(r < n){
sum -= vec1[l].fs;
r++;
sum += vec1[r].fs;
if(sum >= a and sum <= 2 * a){
for(int i = l; i <= r; i++) res.pb(vec[i].sc);
answer(res);
}
l++;
}
sum = 0;
vector<int> vec2;
for(int i = 0; i < k - 1; i++) sum += vec[i].fs, vec2.pb(i);
sum += val;
vec2.pb(i);
if(sum < 2 * a) answer(vec2);
impossible();
}
signed main(){
}