제출 #953817

#제출 시각아이디문제언어결과실행 시간메모리
953817asdasdqwerA Difficult(y) Choice (BOI21_books)C++14
100 / 100
1 ms1368 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. // vector<long long> vals; long long query(int i) { if (vals[i] == -1) { vals[i] = skim(i+1); } return vals[i]; } void solve(int N, int K, long long A, int S) { vals.assign(N, -1); int l = 0, r = N - K; int cand = -1; while (l <= r) { int m; if (r-l >= 100) { m = l + (r-l)/4; } else { m = l + (r-l)/2; } long long tmpSum = 0; for (int i=K-1;i>=0;i--) { if (tmpSum + (i+1)*query(m+i) < A) { tmpSum = -10; break; } tmpSum += query(i+m); if (tmpSum + i > 2LL*A) { tmpSum = 2LL*A + 1LL; break; } } 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; cand = m; } } long long possum = query(cand + K - 1); for (int i=0;i<K-1;i++) { possum += query(i); } if (A <= possum && possum <= 2*A) { vector<int> idx; for (int i=0;i<K-1;i++) idx.push_back(i+1); idx.push_back(cand+K); answer(idx); 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...