Submission #724640

#TimeUsernameProblemLanguageResultExecution timeMemory
724640gagik_2007A Difficult(y) Choice (BOI21_books)C++17
20 / 100
234 ms1072 KiB
#include "books.h" #include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <ctime> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <limits> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <random> using namespace std; typedef long long ll; typedef long double ld; typedef ll itn; #define ff first #define ss second const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const ll MOD3 = 32768; const ll NNN = 100007; ll n, k, a, s; ll p[100007]; void ansfrom(int st) { vector<int>v; for (int i = st; i < st + k; i++) { v.push_back(i + 1); } answer(v); exit(0); } void check(ll sum, int st) { if (sum >= a && sum <= 2 * a)ansfrom(st); } ll skimm(int ind) { if (p[ind] != -1)return p[ind]; return p[ind] = skim(ind); } ll sum_from(int ind) { ll res = 0; for (int i = ind; i < ind + k; i++) { res += skimm(i); } return res; } void solve(int N, int K, long long A, int S) { n = N; k = K; a = A; s = S; if (n == s) { ll sum = 0; ll least = -1; for (int i = 0; i < n; i++) { p[i] = skim(i + 1); if (i < k - 1)sum += p[i]; else if (p[i] > a && least == -1)least = i; } if (least != -1 && sum + p[least] >= a && sum + p[least] <= 2 * a) { vector<int>v; for (int i = 0; i < k - 1; i++) { v.push_back(i + 1); } v.push_back(least + 1); answer(v); return; } else { sum += p[k - 1]; check(sum, 0); for (int i = k; i < n; i++) { sum -= p[i - k]; sum += p[i]; check(sum, i - k + 1); } impossible(); return; } } else if (s >= 170) { ll sum = 0; vector<int>v; for (int i = 1; i <= n; i++) { p[i] = -1; } for (int i = 0; i < k - 1; i++) { sum += skimm(i + 1); v.push_back(i + 1); } if (sum + skimm(k) > 2 * a || sum + skimm(n) < a) { impossible(); return; } int l = k, r = n; /*while (l < r) { int m = (l + r) / 2; if (skimm(m) >= a) { r = m; } else { l = m + 1; } } ll val = sum + skimm(l); if (val >= a && val <= 2 * a) { v.push_back(l); answer(v); return; }*/ l = 1, r = n - k; while (l < r) { int mid = (l + r) / 2; sum = sum_from(mid); if (a <= sum && sum <= 2 * a) { ansfrom(mid); } else if (a > sum) { l = mid + 1; } else { r = mid; } } sum = sum_from(l); if (a <= sum && sum <= 2 * a) { ansfrom(l); } impossible(); return; } }
#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...