oj.uz

Submission #90012

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


int find_best(int n) {
    int N=2e5+5;
    int lo=(int)sqrt(N);
    int maxx=0;
    for(int i=0;i<lo;i++)
    {
        vector<int> tr=ask(i);
        int t=tr[0]+tr[1];
        if(t==0)
            return i;
        maxx=max(maxx,t);
    }
    int nasao=0;
    int last=n-1;
    while(true)
    {
        int l=last,r=last;
        while(l<r)
        {
            int m=(l+r)>>1;
            vector<int> tr=ask(m);
            int t=tr[0]+tr[1];
            if(t==0)
                return m;
            if(t!=maxx)
            {
                l=m;
                continue;
            }
            if(tr[1]>nasao)
                l=m+1;
            else
                r=m-1;
        }
        vector<int> tr=ask(l);
        int t=tr[0]+tr[1];
        if(t==0)
            return l;
        last=l-1;
        nasao++;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 296 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 588 KB Incorrect
2 Halted 0 ms 0 KB -