Submission #1089704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089704		urd05	The Big Prize (IOI17_prize)	C++17	100 / 100	30 ms	2256 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;
int mxv;

void solve(int l,int r,int k,int y) {
    if (l>r||k==0) {
        return;
    }
    int mid=(l+r)/2;
    P got=query(mid);
    if (got.first+got.second==mxv) {
        solve(l,mid-1,y-got.second,y);
        solve(mid+1,r,k-(y-got.second),got.second);
        return;
    }
    vec.push_back(mid);
                if (got.first+got.second==0) {
                return;
            }
    int cnt=1;
    for(int i=mid-1;i>=l;i--) {
        P got=query(i);
        if (got.first+got.second==mxv) {
            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);
                        if (got.first+got.second==0) {
                return;
            }
            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 ind=450;
	int cnt=0;
	set<int> s;
	for(int i=0;i<480;i++) {
	    P got=query(i);
	    s.insert(got.first+got.second);
	    int y=(*s.rbegin());
	    if (s.size()==5||y>40) {
	        int mx=*s.rbegin();
	        mxv=mx;
	        for(int j=0;j<=i;j++) {
	            if (save[j].first+save[j].second!=mx) {
	                vec.push_back(j);
	                cnt--;
	            }
	            else {
	                cnt=save[j].second;
	            }
	        }
	        ind=i+1;
	        break;
	    }
	    if (i==479||i==n-1) {
	        ind=i+1;
	        int mx=*s.rbegin();
	        mxv=mx;
	        for(int j=0;j<=i;j++) {
	            if (save[j].first+save[j].second!=mx) {
	                vec.push_back(j);
	                cnt--;
	            }
	            else {
	                cnt=save[j].second;
	            }
	        }
	        break;
	    }
	}
	for(int x:vec) {
	    if (query(x)==P(0,0)) {
	        return x;
	    }
	}
	solve(ind,n-1,cnt,cnt);
	for(int x:vec) {
	    if (query(x)==P(0,0)) {
	        return x;
	    }
	}
	return 0;
}

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