Submission #1089694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089694		urd05	The Big Prize (IOI17_prize)	C++17	0 / 100	50 ms	2296 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
int n;
P save[200005];

P query(int i) {
    if (save[i].first!=-1) {
        return save[i];
    }
    vector<int> got=ask(i);
    return save[i]=P(got[0],got[1]);
}

vector<int> vec;

void solve(int l,int r,int k,int y) {
    if (l>r) {
        return;
    }
    int mid=(l+r)/2;
    P got=query(mid);
    if (got.first+got.second==n-1) {
        solve(l,mid-1,y-got.second,y);
        solve(mid+1,r,k-(y-got.second),got.second);
        return;
    }
    vec.push_back(mid);
    int cnt=1;
    for(int i=mid-1;i>=l;i--) {
        P got=query(i);
        if (got.first+got.second==n-1) {
            solve(l,i-1,y-got.second,y);
            solve(mid+1,r,k-(y-got.second)-cnt,got.second-cnt);
            return;
        }
        else {
            vec.push_back(i);
            cnt++;
        }
    }
    solve(mid+1,r,k-cnt,y-cnt);
}

int find_best(int N) {
    n=N;
	for(int i = 0; i < n; i++) {
	    save[i]=P(-1,-1);
	}
	int i=0;
	int y=0;
	int cnt=0;
	while (i<n) {
	    P got=query(i);
	    if (got.first+got.second==n-1) {
	        y=got.first;
	        cnt=got.second;
	        break;
	    }
	    else {
	        vec.push_back(i);
	    }
	    i++;
	}
	solve(i+1,n-1,cnt,y);
	for(int x:vec) {
	    if (query(x)==P(0,0)) {
	        return x;
	    }
	}
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80