Submission #982197

#	Time	Username	Problem	Language	Result	Execution time	Memory
982197		SiliconSquared	The Big Prize (IOI17_prize)	C++14	100 / 100	24 ms	1524 KiB

prize

#include "prize.h"
using namespace std;
#include <vector>

int z,r,y;
bool e;
vector<int> g;

bool f(int a,int b){
    if (e){return false;}
    if (g[a]==g[b]){
        return false;
    }
    vector<int> p={-1,-1};
    if (a+1==b){
        p=ask(a);
        if (p==(vector<int>){0,0}){
            r=a;
            return true;
        }
        if (p[0]+p[1]>z){
            e=true;
            z=p[0]+p[1];
        }
        return false;
    }
    int m=(a+b)/2;
    while ((p[0]+p[1])!=z){
        if (m==b){
            p[0]=g[b];
            g[m-1]=g[b]-1;
            m++;
            break;
        }
        p=ask(m);
        if (p[0]==0&&p[1]==0){
            r=m;
            return true;
        }
        if (p[0]+p[1]>z){
            e=true;
            z=p[0]+p[1];
            return false;
        }
        m++;
    }
    m--;
    if (m!=b){
        g[m]=p[0];
    }
    g[(a+b)/2]=p[0]-m+(a+b)/2;
    if (f(a,(a+b)/2)){
        return true;
    }
    if (f(m,b)){
        return true;
    }
    return false;
}

int find_best(int n) {
    g.resize(n);
    g[0]=0;
    z=ask(n-1)[0];
    if (z==0){
        return n-1;
    }
    g[n-1]=z;
    y=n-1;
    e=false;
    f(0,n-1);
    vector<int> p;
    while (e){
        y--;
        p=ask(y);
        if (p[0]+p[1]==0){
            return y;
        }
        if (p[0]+p[1]>z){
            z=p[0]+p[1];
        }
        if (p[0]+p[1]==z){
            g[y]=p[0];
            e=false;
            f(0,y);
        }
    }
    return r;
}

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