제출 #1067276

#제출 시각아이디문제언어결과실행 시간메모리
1067276duckindogA Difficult(y) Choice (BOI21_books)C++17
60 / 100
3017 ms2464 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; namespace sub5 { void solve(int n, int k, long long a, int s) { vector<long long> x(n + 1); vector<int> ret; { // k - 1 long long total = 0; for (int i = 1; i < k; ++i) { if (!x[i]) x[i] = skim(i); total += x[i]; } auto get = [&](int i) { if (!x[i]) x[i] = skim(i); return total + x[i]; }; int l = k, r = n; while (l <= r) { int mid = l + r >> 1; auto value = get(mid); if (a <= value && value <= 2 * a) { for (int i = 1; i < k; ++i) ret.push_back(i); ret.push_back(mid); answer(ret); return; } if (value < a) l = mid + 1; else r = mid - 1; } } { //consecutive auto get = [&](int l, int r) { long long total = 0; for (int i = l; i <= r; ++i) { if (!x[i]) x[i] = skim(i); total += x[i]; } return total; }; int l = k, r = n; while (l <= r) { int mid = l + r >> 1; auto value = get(mid - k + 1, mid); if (a <= value && value <= 2 * a) { for (int i = mid - k + 1; i <= mid; ++i) ret.push_back(i); answer(ret); return; } if (value < a) l = mid + 1; else r = mid - 1; } } impossible(); } } void solve(int n, int k, long long a, int s) { if (s >= 170) { sub5::solve(n, k, a, s); return; } vector<long long> x(n + 1); vector<bool> mk(n + 1); long long total = 0, cnt = k; for (int i = 1; i <= k; ++i) { if (!x[i]) x[i] = skim(i); mk[i] = true; total += x[i]; } auto done = [&]() { vector<int> ret; if (a <= total && total <= 2 * a) { for (int i = 1; i <= n; ++i) if (mk[i]) ret.push_back(i); answer(ret); exit(0); } }; for (;;) { done(); vector<int> pool; for (int i = 1; i <= n; ++i) if (!mk[i]) pool.push_back(i); if (!pool.size()) break; for (int i = 1; i <= n; ++i) { if (mk[i]) { total -= x[i]; mk[i] = false; break; } } int l = 0, r = pool.size() - 1; while (l <= r) { if (cnt == s) break; int mid = l + r >> 1; if (!x[pool[mid]]) { x[pool[mid]] = skim(pool[mid]); cnt += 1; } mk[pool[mid]] = true; done(); mk[pool[mid]] = false; if (total + x[pool[mid]] <= 2 * a) l = mid + 1; else r = mid - 1; } } impossible(); }

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'void sub5::solve(int, int, long long int, int)':
books.cpp:25:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid = l + r >> 1;
      |                   ~~^~~
books.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:107:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |       int mid = l + r >> 1;
      |                 ~~^~~
#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...