제출 #425272

#제출 시각아이디문제언어결과실행 시간메모리
425272NachoLibre커다란 상품 (IOI17_prize)C++17
0 / 100
18 ms11240 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); } vvint cch; vint A(int i) { if(cch[i][0] == -1) cch[i] = ask(i); return cch[i]; } int find_best(int n) { cch.resize(n, vint(2, -1)); int cm = 0; for(int i = 1; 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 + 1; } } 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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...