제출 #659230

#제출 시각아이디문제언어결과실행 시간메모리
659230jiahng커다란 상품 (IOI17_prize)C++14
90 / 100
88 ms6440 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 (l == r){ query(l); if (sm[l] == 0) return l; return -1; } query(l); query(r); if (sm[r] == sm[l] && memo[l][0] == memo[r][0]) return -1; int m = (l+r)/2; return max(dnc(l,m), dnc(m+1,r)); } const int sqrtn = 472; int find_best(int n) { N = n; return dnc(0,N-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...