제출 #724710

#제출 시각아이디문제언어결과실행 시간메모리
724710gagik_2007A Difficult(y) Choice (BOI21_books)C++17
20 / 100
244 ms976 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(ll st) { vector<int>v; for (ll i = st; i < st + k; i++) { v.push_back(i + 1); } answer(v); exit(0); } void check(ll sum, ll st) { if (sum >= a && sum <= 2 * a)ansfrom(st); } ll skimm(ll ind) { if (p[ind] != -1)return p[ind]; return p[ind] = skim(ind); } ll sum_from(ll ind) { ll res = 0; for (ll i = ind; i < ind + k; i++) { res += skimm(i); } return res; } void solve(int N, int K, ll A, int S) { n = N; k = K; a = A; s = S; if (n == s) { ll sum = 0; ll least = -1; for (ll 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 (ll 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 (ll 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 (ll i = 1; i <= n; i++) { p[i] = -1; } for (ll i = 0; i < k - 1; i++) { sum += skimm(i + 1); v.push_back(i + 1); } if (sum + skimm(k) > 2 * a) { impossible(); return; } ll l = k, r = n + 1; while (l < r) { ll m = (l + r) / 2; if (skimm(m) >= a) { r = m; } else { l = m + 1; } } int ind = l; //cout << "ind: " << ind << endl; ll val = sum + skimm(l); if (val >= a && val <= 2 * a) { v.push_back(l); answer(v); return; } if (2 * k >= ind) { l = 1, r = ind - k + 1; while (l < r) { ll mid = (l + r) / 2; sum = sum_from(mid); //cout << mid << ": " << sum << ": " << sum - a << endl; if (a <= sum && sum <= 2 * a) { ansfrom(mid - 1); } else if (a > sum) { l = mid + 1; } else { r = mid; } } sum = sum_from(l); //cout << l << ": " << sum << ": " << sum - a << endl; if (a <= sum && sum <= 2 * a) { ansfrom(l - 1); } impossible(); return; } else { sum = 0; for (int i = 1; i <= k; i++) { sum += skimm(i); } //cout << "sum: " << sum << endl; int i = 1; int j = ind - k; if (a <= sum && sum <= 2 * a) { v.clear(); for (int p = i; p <= k; p++) { v.push_back(p); } for (int p = ind - k; p < j; p++) { v.push_back(p); } answer(v); return; } while (j < ind) { sum -= skimm(i); i++; sum += skimm(j); j++; //cout << "sum: " << sum << endl; //cout << i << " " << j << endl; if (a <= sum && sum <= 2 * a) { v.clear(); for (int p = i; p <= k; p++) { v.push_back(p); } for (int p = ind - k; p < j; p++) { v.push_back(p); } answer(v); return; } } 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...