# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1036243 | 2024-07-27T06:54:22 Z | Alihan_8 | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KB |
#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; } 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]; }; int ans = -1; if ( rand(0, 1) ){ for ( int i = n - 1; i >= 0; i-- ){ auto c = f(i); if ( c[0] + c[1] == 0 ){ ans = i; return ans; } int l = 0, r = i; while ( l < r ){ int m = (l + r) / 2; if ( f(m) != c ){ l = m + 1; } else r = m; } i = l; } } else{ for ( int i = 0; i < n; i++ ){ auto c = f(i); if ( c[0] + c[1] == 0 ){ ans = i; return ans; } int l = i, r = n; while ( l + 1 < r ){ int m = (l + r) / 2; if ( f(m) != c ){ r = m; } else l = m; } i = l; } } assert(false); }