제출 #1043243

#제출 시각아이디문제언어결과실행 시간메모리
1043243Alihan_8커다란 상품 (IOI17_prize)C++17
94.91 / 100
31 ms5672 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' //#define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int B = 474; int find_best(int n){ vector <vector<int>> dp(n); auto f = [&](int j){ if ( dp[j].empty() ){ dp[j] = ask(j); } return dp[j]; }; auto g = [&](int j){ return f(j)[0] + f(j)[1]; }; int mx = -1, k = -1; for ( int i = 0; i < min(n, B); i++ ){ if ( chmax(mx, g(i)) ){ k = i; } if ( g(i) == 0 ){ return i; } } for ( int i = k; i < n;){ int l = i, r = min(n, l + B); if ( f(l) == f(r - 1) ){ i = r - 1; continue; } while ( l + 1 < r ){ int m = (l + r) / 2; if ( f(m)[1] != f(i)[1] ){ r = m; } else l = m; } int j = r; while ( j < n && g(j) != g(i) ){ if ( g(j) == 0 ){ return j; } j++; } i = j; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...