# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
961415 | 2024-04-12T04:42:41 Z | steveonalex | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; typedef unsigned long long ull; #define ALL(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng(1); ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;} ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll LASTBIT(ll mask){return mask & (-mask);} ll pop_cnt(ll mask){return __builtin_popcountll(mask);} ll ctz(ll mask){return __builtin_ctzll(mask);} ll clz(ll mask){return __builtin_clzll(mask);} ll logOf(ll mask){return 63 - clz(mask);} template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b){a = b; return true;} return false; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b){a = b; return true;} return false; } template <class T> void printArr(T& a, string separator = " ", string finish = "\n"){ for(auto i: a) cout << i << separator; cout << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } // int n; // vector<ll> a; void solve(int n, int k, long long A, int S) { vector<ll> a(n+1); int l = 0, r = n - k + 1; while(l < r){ int mid = (l + r + 1) >> 1; if (a[mid] == 0) a[mid] = skim(mid); if (a[mid] * k + k * (k-1) / 2 <= 2 * A) l = mid; else r = mid - 1; } int x = l; if (x == 0){impossible(); return;} int l = max(1, x - k), r = min(n, x + k); for(int i = l; i<=r; ++i){ if (a[i] == 0) a[i] = skim(i); } for(int i = l; i<=r-k+1; ++i){ vector<int> ans; for(int j = 0; j < k; ++j) ans.push_back(i + j); ll sum = 0; for(int j = 0; j<k; ++j) sum += a[ans[j]]; if (sum >= A && sum <= 2 * A) { answer(ans); return; } } impossible(); } // int main(void){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // return 0; // }