Submission #943283

#TimeUsernameProblemLanguageResultExecution timeMemory
943283teacupA Difficult(y) Choice (BOI21_books)C++14
100 / 100
1 ms1368 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; #define ll long long #define ii pair<int,int> #define vi vector<int> typedef vector<ii> vii; // // --- 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. // void solve(int N, int K, long long A, int S) { // TODO implement this function vector<long long> V(N+5); vector<int> ans; for (int i=0; i<N+5; i++) V[i]=-1; long long sum=0; for (int i=1; i<=K; i++){ V[i]=skim(i); sum+=V[i]; } if (sum>2*A){ impossible(); }else if (sum>=A){ //answer!! ans.clear(); for (int i=1; i<=K; i++){ ans.push_back(i); } answer(ans); }else{ //sum<A ans.clear(); //binary search from K+1 to N ll L=1, R=N+1, M; while (L<R) { M = (L+R)/2; ll temp; if(V[M] != -1) temp = V[M]; else temp = skim(M); V[M] = temp; if (temp < A) L = M+1; else R = M; } if (L < K) impossible(); if (L <= N){ ll temp; if(V[L] != -1) temp = V[L]; else temp = skim(L); V[L] = temp; if(sum - V[K] + temp <= 2*A){ ans.clear(); for(int i=1; i<K; i++){ ans.push_back(i); } ans.push_back(L); answer(ans); } N = L - 1; } set<int> S_; for(int i=1; i<=K; i++){ S_.insert(i); } for(int i=0; i<K; i++){ S_.erase(K - i); S_.insert(N - i); ll temp; if(V[N - i] != -1) temp = V[N - i]; else temp = skim(N - i); V[N - i] = temp; sum -= V[K - i]; sum += temp; if(A <= sum && sum <= 2*A){ ans.clear(); for(int i : S_){ ans.push_back(i); } answer(ans); } } 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...