제출 #703549

#제출 시각아이디문제언어결과실행 시간메모리
703549SamNguyen커다란 상품 (IOI17_prize)C++14
98.40 / 100
53 ms5300 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 { vector<int> inds; 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) { inds.push_back(i); i++; continue; } const int T = 1001; int j = FIND_LARGEST(i, min(n - 1, i + T), [&](int j) { return count(j) == count(i); }); // if (j > i + T) // cout << "Nah." << endl; // if (j > i + T + 1) // j = FIND_LARGEST(i + T + 1, n - 1, [&](int j) { return count(j) == count(i); }); // int j = FIND_LARGEST(i, n - 1, [&](int j) { return count(j) == count(i); }); cnt++; i = j + 1; } // cout << "cnt = " << cnt << endl; } int find_best(int _n) { n = _n; cnt.assign(n, vector<int>()); try { MAX_S = count_both(0); 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...