oj.uz

Submission #137517

# Submission time Handle Problem Language Result Execution time Memory
137517 2019-07-28T05:59:38 Z ckodser The Big Prize (IOI17_prize) C++14
0 / 100
 7 ms 5112 KB 
#include "prize.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2e5+500;
const ll inf=1e9+900;

vector<ll>  ansS[maxn];
ll mx=0;
vector<ll>  ASK(ll x){
    if(ansS[x].size())return ansS[x];
    ansS[x]=ask(x);
    mx=max(mx,ansS[x][0]+ansS[x][1]);
    return ansS[x];
}
ll N;
ll fmx;
ll bild(ll l,ll r,ll L,ll R){
    l=max(l,0);
    r=min(r,N);
    if(l>=r)return -1;
    if(L+R==mx)return -1;
    ll mid=(l+r)/2;
    for(ll i=mid;i<r;i++){
	vector<ll> vec=ASK(i);
	if(mx!=fmx)return -2;
	if(vec[0]+vec[1]==mx){
	    ll XX=bild(l,mid,L,vec[1]+(mid-i)); 
	    if(XX==-2)return -2;
	    if(XX!=-1)return XX;
	    XX=bild(i+1,r,vec[0],R);
	    if(XX==-2)return -2;
	    if(XX!=-1)return XX;
	    return -1;
	}else{
	    if(vec[0]+vec[1]==0)return i;
	}
    }
    return bild(l,mid,L,R+(r-mid));
}

int find_best(int n) {
    N=n;
    if(n<=5000){
	for(ll i=0;i<n;i++){
	    vector<ll> vec=ask(i);
	    if(vec[0]+vec[1]==0)return i;
	}
    }
    ASK(0);
    while(1){
	fmx=mx;
	ll x=bild(0,n,0,0);
	if(x!=-2)return x;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 5112 KB Integer -1 violates the range [0, 199999]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Correct 7 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Integer -1 violates the range [0, 199999]
7 Halted 0 ms 0 KB -