oj.uz

Submission #963566

# Submission time Handle Problem Language Result Execution time Memory
963566 2024-04-15T10:36:28 Z Ahmed57 The Big Prize (IOI17_prize) C++17
0 / 100
 0 ms 344 KB 
#include "bits/stdc++.h"
using namespace std;
#include "prize.h"

#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
pair<int,int> ret[200001];
int fin = -1;
pair<int,int> ans(int x){
    if(ret[x].first!=-1)return ret[x];
  	vector<int>lol = ask(x);
    ret[x] = {lol[0],lol[1]}; 
    if(ret[x].first==ret[x].second&&ret[x].first==0){
        fin = x;
    }
    return ret[x];
}
void solve(int l,int r){
    if(fin!=-1)return ;
    if(l>r)return ;
    if(l==r){
        ans(l);
        return ;
    }
    while(ans(l).first+ans(l).second!=ans(r).first+ans(r).second){
        while(ans(l).first+ans(l).second<ans(r).first+ans(r).second)l++;
        while(ans(l).first+ans(l).second>ans(r).first+ans(r).second)r--;
    }
    int mid = (l+r)/2;
    if(ans(l).second==ans(r).second){
        return ;
    }
    solve(l,mid);
    solve(mid+1,r);
}
int find_best(int n){
    solve(0,n-1);
    return fin;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -