제출 #398892

#제출 시각아이디문제언어결과실행 시간메모리
398892couplefireA Difficult(y) Choice (BOI21_books)C++17
0 / 100
1 ms680 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; void solve(int n, int k, long long goal, int s){ 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+1); if(val < goal) pos = n; vector<int> ans, arr(n, 0); if(pos < k-1){ impossible(); return; } if(pos != n){ long long sum = 0; for(int i = 0; i<k-1; i++) sum += (arr[i] ? arr[i] : arr[i] = 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; } } for(int i = 0; i<k; i++) arr[i] = (arr[i] != 0 ? arr[i] : arr[i] = skim(i+1)); for(int i = pos-1; i>=pos-k; i--) arr[i] = (arr[i] != 0 ? arr[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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...