제출 #436851

#제출 시각아이디문제언어결과실행 시간메모리
436851davitmargA Difficult(y) Choice (BOI21_books)C++17
20 / 100
3 ms1140 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <random> #include <bitset> #include <stack> #include <cassert> #include <iterator> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; #ifndef death #include "books.h" #endif // death const int N = 500005; #ifdef death LL A[N]; LL skim(int i) { cout << "? " << i << endl; LL res = A[i]; //cin >> res; return res; } void answer(vector<int> v) { cout << "!"; for (int i = 0; i < v.size(); i++) cout << " " << v[i]; cout << endl; } void impossible() { cout << "! -1" << endl; } #endif int rnd() { return (rand() << 32) + rand(); } int rnd(int l, int r) { int d = r - l + 1; return l + rnd() % d; } int n, k, s; LL X, a[N], sum, pr[N]; vector<int> ans; int used[N]; LL mySkim(int pos) { if (!used[pos]) { used[pos] = 1; a[pos] = skim(pos); } return a[pos]; } vector<int> lr(int l, int r) { vector<int> res; for (int i = l; i <= r; i++) res.push_back(i); return res; } LL get(int l, int r) { LL p = r - l + 1ll; LL sum = 0; int steps = min(70, r - l + 1); int d = p / steps; for (int i = 0; i < steps; i++) { sum += skim(r - d * i) * p; } sum /= steps; return sum; } bool check(LL val) { return (val >= X && val <= X + X); } void solve(int NN, int K, long long A, int S) { n = NN; k = K; X = A; s = S; int l = k, r = n, m, pos = n + 1; while (l <= r) { m = (l + r) / 2; mySkim(m); if (a[m] >= X) { pos = m; r = m - 1; } else l = m + 1; } if (pos < k) { impossible(); return; } for (int i = 1; i <= k; i++) mySkim(i); for (int i = pos - 1; i >= pos - k && i >= 1; i--) mySkim(i); for (int i = 1; i <= n; i++) pr[i] = pr[i - 1] + a[i]; if (check(pr[k - 1] + a[pos])) { ans = lr(1, k - 1); ans.push_back(pos); answer(ans); return; } if (check(pr[k])) { ans = lr(1, k); answer(ans); return; } pos--; if (pos < k) { impossible(); return; } if (check(pr[pos] - pr[pos - k])) { ans = lr(pos-k+1, pos); answer(ans); return; } for (int i = 1; i < k; i++) { if (check(pr[k] - pr[i] + pr[pos] - pr[pos - i])) { ans = lr(i + 1, k); vector<int> x = lr(pos - i + 1, pos); for (int j = 0; j < x.size(); j++) ans.push_back(x[j]); answer(ans); return; } } impossible(); } #ifdef death int main() { fastIO; int nn, kk, aa; cin >> nn >> kk >> aa; for (int i = 1; i <= nn; i++) cin >> A[i]; solve(nn, kk, aa, 100); return 0; } #endif // death /* 8 3 110 1 3 5 10 40 60 70 105 */

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

books.cpp: In function 'int rnd()':
books.cpp:67:17: warning: left shift count >= width of type [-Wshift-count-overflow]
   67 |  return (rand() << 32) + rand();
      |          ~~~~~~~^~~~~
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:193:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |    for (int j = 0; j < x.size(); j++)
      |                    ~~^~~~~~~~~~
#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...