제출 #703577

#제출 시각아이디문제언어결과실행 시간메모리
703577SamNguyen커다란 상품 (IOI17_prize)C++14
90 / 100
73 ms5304 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; template <class T1, class T2> inline bool minimise(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } template <class T1, class T2> inline bool maximise(T1 &x, T2 y) { if (x < y) { x = y; return true; } return false; } template <class F> int FIND_SMALLEST(int l, int r, F f) { int res = r + 1; while (l <= r) { int m = (l + r) / 2; if (f(m)) res = m, r = m - 1; else l = m + 1; } return res; } template <class F> int FIND_LARGEST(int l, int r, F f) { int res = l - 1; while (l <= r) { int m = (l + r) / 2; if (f(m)) res = m, l = m + 1; else r = m - 1; } return res; } namespace SUB1 { int find_best(int n) { int l = 0, r = n - 1; while (l <= r) { int m = (l + r) >> 1; auto cnt = ask(m); if (cnt[0] == cnt[1]) return m; if (cnt[0] < cnt[1]) l = m + 1; else r = m - 1; } return -1; } } namespace SUB2A { int n, MAX_S; vector<vector<int>> cnt; vector<int>& count(int i) { if (cnt[i].empty()) cnt[i] = ask(i); return cnt[i]; } int count_both(int i) { auto &a = count(i); int res = a[0] + a[1]; if (res == 0) throw i; return res; } void extract_inds() { int cnt = 0; for (int i = 0; i < n; ) { if (count_both(i) < MAX_S) { i++; continue; } int k = FIND_LARGEST(0, log2(n - i) + 1, [&](int k) { return i + (1 << k) < n and count(i + (1 << k)) == count(i); }); // cerr << "i = " << i << " -> k = " << k << endl; while (k >= 0) { if (i + (1 << k) < n and count(i + (1 << k)) == count(i)) i += 1 << k; k--; } cnt++; i++; } // cout << "cnt = " << cnt << endl; } int find_best(int _n) { n = _n; cnt.assign(n, vector<int>()); try { MAX_S = 0; for (int i = 0; i < 3 and i < n; i++) maximise(MAX_S, count_both(i)); extract_inds(); } catch (int i) { return i; } return -1; } } int find_best(int n) { return SUB2A::find_best(n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...