제출 #425277

#제출 시각아이디문제언어결과실행 시간메모리
425277NachoLibre커다란 상품 (IOI17_prize)C++17
20 / 100
129 ms22644 KiB
#include <bits/stdc++.h> using namespace std; #define sz(a) ((int)(a).size()) typedef vector<int> vint; typedef vector<vint> vvint; typedef long long ll; #ifndef wambule #include "prize.h" #else int _n; vint _x; vint ask(int i) { vint dr(2); for(int j = 0; j < _n; ++j) { if(_x[j] < _x[i]) ++dr[j > i]; } return dr; } #endif mt19937_64 rnd(time(0)); int R(int l, int r) { return l + rnd() % (r - l + 1); } int c; vvint cch; vint A(int i) { if(cch[i][0] == -1) cch[i] = ask(i), ++c; assert(c < 10000); return cch[i]; } int find_best(int n) { cch.resize(n, vint(2, -1)); int cm = 0; for(int i = 0; i < 30; ++i) { int x = R(0, n - 1); cm = max(cm, A(x)[0] + A(x)[1]); if(A(x)[0] + A(x)[1] == +0) return x; } for(int i = 0; i < n; ++i) { if(A(i)[0] + A(i)[1] == +0) return i; if(A(i)[0] + A(i)[1] == cm) { int l = i, r = n - 1; while(l < r) { int m = l + r + 1 >> 1; while(A(m)[0] + A(m)[1] < cm) { --m; r = m; } if(A(m)[1] == A(i)[1]) l = m; else r = m - 1; } i = l; } } return 0; } #ifdef wambule int main() { ios::sync_with_stdio(0); cin.tie(0); _x = {3, 2, 3, 1, 3, 3, 2, 3}; _n = _x.size(); cout << find_best(_n) << endl; return 0; } #endif

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...