제출 #953745

#제출 시각아이디문제언어결과실행 시간메모리
953745asdasdqwerA Difficult(y) Choice (BOI21_books)C++14
60 / 100
135 ms1992 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; // // --- 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 subtask2(int N, int K, long long A, int S) { vector<long long> a(N); for (int i=0;i<N;i++) { a[i] = skim(i+1); } long long pref = 0; for (int i=0;i<K;i++) { pref += a[i]; } if (pref > 2*A) { impossible(); return; } auto it = lower_bound(a.begin(), a.end(), A); if (it != a.end()) { long long num = *it; for (int i=0;i<K-1;i++) num += a[i]; if (num <= 2LL*A) { vector<int> idx; for (int i=0;i<K-1;i++) idx.push_back(i+1); idx.push_back(distance(a.begin(), it)+1); answer(idx); return; } } while (a.back() >= A)a.pop_back(); for (int i=0;i<(int)a.size()-K+1;i++) { long long sum = 0; for (int j=0;j<K;j++) { sum += a[j+i]; } if (A <= sum && sum <= 2LL*A) { vector<int> idx; for (int j=0;j<K;j++) { idx.push_back(i+j+1); } answer(idx); return; } } impossible(); } vector<long long> vals; int toge; int qu; long long query(int i) { if (vals[i] == -1) { qu++; assert(qu <= toge); vals[i] = skim(i+1); } return vals[i]; } void solve(int N, int K, long long A, int S) { toge = S; qu=0; if (N <= S) { subtask2(N,K,A,S); return; } vals.assign(N, -1); // check first K values long long sum = 0; for (int i=0;i<K;i++) { sum += query(i); } if (sum > 2LL*A) { impossible(); return; } if (sum >= A) { vector<int> idx; for (int i=0;i<K;i++) { idx.push_back(i+1); } answer(idx); return; } // binary search for the first value greater or equal to A int l = K, r = N-1; int ans = -1; long long valans = -1; while (l <= r) { int m = l + (r-l)/2; long long val = query(m); if (val == A) { ans = m; valans = A; break; } if (val < A) { l = m+1; } else { ans = m; valans = val; r = m-1; } } // check if prefix + a is fitting int last = N-1; if (ans != -1) { long long cand = sum - query(K-1) + valans; long long cand2 = sum - query(0) + valans; if (A <= cand && cand <= 2LL*A) { vector<int> idx; for (int i=0;i<K-1;i++)idx.push_back(i+1); idx.push_back(ans+1); answer(idx); return; } if (A <= cand2 && cand2 <= 2LL*A) { vector<int> idx; for (int i=1;i<K;i++)idx.push_back(i+1); idx.push_back(ans+1); answer(idx); return; } last = ans-1; } long long suf = 0; for (int i=0;i<K;i++) { suf += query(last - i); } if (A <= suf && suf <= 2LL*A) { vector<int> idx; for (int i=0;i<K;i++) { idx.push_back(last - i + 1); } answer(idx); return; } if (suf < A) { impossible(); return; } // now prefix has sum < a, and suffix has sum > 2*a // then, there must be a subarray, such that the sum is exactly in between // why? because if that wasn't true, then the added contribution must be greater than a // however, since all elements are smaller than a, any difference between two elements cannot be greater // that a, hence, there must be a subarray with the desired sum l = 0, r = last - K + 1; while (l <= r) { int m = l + (r-l)/2; long long tmpSum = 0; for (int i=0;i<K;i++) { tmpSum += query(i+m); } if (A <= tmpSum && tmpSum <= 2LL*A) { vector<int> idx; for (int i=0;i<K;i++)idx.push_back(i+m+1); answer(idx); return; } else if (tmpSum < A) { l = m+1; } else { r = m-1; } } }
#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...