제출 #659216

#제출 시각아이디문제언어결과실행 시간메모리
659216jiahng커다란 상품 (IOI17_prize)C++14
97.55 / 100
58 ms6200 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 200010 #define INF (ll)1e9 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N; vi memo[maxn]; bool queried[maxn]; int sm[maxn]; vi query(int x){ if (queried[x]) return memo[x]; queried[x] = 1; memo[x] = ask(x); sm[x] = memo[x][0] + memo[x][1]; return memo[x]; } bool done = 0; int dnc(int l,int r){ if (done || l > r) return -1; if (queried[r+1] && queried[l-1]){ if (sm[r+1] == sm[l-1] && memo[l-1][0] == memo[r+1][0]) return -1; } int m = (l+r)/2; query(m); if (sm[m] == 0){ done = 1; return m; } return max(dnc(l,m-1), dnc(m+1,r)); } int find_best(int n) { N = n; return dnc(0,n-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...