Submission #574958

#TimeUsernameProblemLanguageResultExecution timeMemory
574958RealSnakeA Difficult(y) Choice (BOI21_books)C++14
15 / 100
18 ms1024 KiB
#include "bits/stdc++.h" using namespace std; #include "books.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define ll long long #define mod 1000000007 void solve(int n, int k, ll a, int S) { if(n <= 1000 && S == n && k == 3) { ll arr[n + 1]; for(int i = 1; i <= n; i++) arr[i] = skim(i); vector<int> ans; set<pair<ll, int>> s; for(int i = n; i >= 1; i--) { for(int j = i - 1; j >= 1; j--) { ll sum = arr[i] + arr[j]; auto it = s.lower_bound({a - sum, 0}); if(it != s.end()) { pair<ll, int> p = *it; sum += p.first; if(sum <= 2 * a) { ans.push_back(i); ans.push_back(j); ans.push_back(p.second); answer(ans); return; } } } s.insert({arr[i], i}); } impossible(); return; } int l = 1, r = n - k + 1; ll arr[n + 1]; for(int i = 1; i <= n; i++) arr[i] = 0; while(l <= r) { int mid = (l + r) / 2; ll x = 0; for(int i = mid; i <= mid + k - 1; i++) { if(!arr[i]) arr[i] = skim(i); x += arr[i]; } if(x >= a && x <= 2 * a) { vector<int> ans; for(int i = mid; i <= mid + k - 1; i++) ans.push_back(i); answer(ans); return; } if(x > a * 2) r = mid - 1; else l = mid + 1; } 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...