제출 #947887

#제출 시각아이디문제언어결과실행 시간메모리
947887willychanA Difficult(y) Choice (BOI21_books)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; // // --- Sample implementation for the task books --- // // To compile this program with the sample grader, place: // books.h books_sample.cpp sample_grader.cpp // in a single folder and run: // g++ books_sample.cpp sample_grader.cpp // in this folder. // map<int,ll> mem; ll get(int k){ if(mem.count(k)) return mem[k]; mem[k] = skim(k); return mem[k]; } void solve(int N, int K, long long A, int S) { int l = 0;int r=N+1; while(r-l>1){ int m = (l+r)/2; if(get(m)>=A) r = m; else l = m; } if(r<=K){ ll sum=0; for(int i=1;i<=K;i++){ sum+=get(i); } if(sum>2*A){ impossible(); return; }else{ vector<int> ans; for(int i=1;i<=K;i++) ans.push_back(i); answer(ans); return ; } } ll sum = 0; for(int i=1;i<K;i++){ sum+=get(i); } sum+=get(r); if(sum<=2*A){ vector<int> ans; for(int i=1;i<K;i++) ans.push_back(i); ans.push_back(r); answer(ans); return ; } sum-=get(r); sum+=get(K); vector<int> stk; for(int i=1;i<=K;i++) stk.push_back(i); vector<int> other; for(int i=r-1;i>=r-K;i--){ if(sum>=A && sum<=2*A) { vector<int> ans; for(auto v : stk) ans.push_back(v); for(auto v : other) ans.push_back(v); answer(ans); return; } int c = stk.back(); stk.pop_back(); sum-=get(c); other.push_back(i); sum+=get(i); } if(sum>=A && sum<=2*A) { vector<int> ans; for(auto v : stk) ans.push_back(v); for(auto v : other) ans.push_back(v); answer(ans); return; } impossible(); return ; }
#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...