oj.uz

Submission #90019

# Submission time Handle Problem Language Result Execution time Memory
90019 2018-12-19T17:35:21 Z nikolapesic2802 The Big Prize (IOI17_prize) C++14
0 / 100
 12 ms 9720 KB 
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

const int N=2e5+5;
map<int,vector<int> > mapa[N];
int sol=-1;
void solve(int l,int r)
{
    if(sol!=-1)
        return;
    int m=(l+r)>>1;
    vector<int> cur=ask(m);
    int sum=cur[0]+cur[1];
    if(sum==0)
    {
        sol=m;
        return;
    }
    if(l==r)
    {
        mapa[sum][m]=cur;
        return;
    }
    int left=1,right=1;
    auto it=mapa[sum].upper_bound(m);
    if(it!=mapa[sum].end())
    {
        if(it->second[0]==cur[0])
            right=0;
    }
    if(it!=mapa[sum].begin())
        it--;
    if(it!=mapa[sum].begin())
    {
        if(it->second[1]==cur[1])
            left=0;
    }
    mapa[sum][m]=cur;
    if(left)
        solve(l,m-1);
    if(right)
        solve(m+1,r);
}
int find_best(int n) {
    solve(0,n-1);
    return sol;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 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 12 ms 9720 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -