# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
299013 | Batyr | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int>
const int maxn=2e5+5;
int dp[maxn][3],ans;
queue<pii>q;
int find_best(int n){
memset(dp,-1,sizeof(dp));
q.push({0,n-1});
while(!q.empty()){
int l=q.top().ff;
int r=q.top().ss;
q.pop();
if(dp[l][0]==-1 and dp[l][1]==-1){
vector<int> p=ask(l);
dp[l][0]=p[0];
dp[l][1]=p[1];
}
if(dp[l][0]+dp[l][1] == 0) return l;
if(dp[r][0]==-1 and dp[r][1] == -1){
vector<int> p=ask(r);
dp[r][0]=p[0];
dp[r][1]=p[1];
}
if(dp[r][0]+dp[r][1] == 0) return r;
if(dp[l][0]+dp[l][1]==dp[r][0]+dp[r][1] and dp[r][0]-dp[l][0] == 0) continue;
q.push({l,(l+r)/2});
q.push({(l+r)/2+1,r});
}
}