Submission #560430

#	Time	Username	Problem	Language	Result	Execution time	Memory
560430		neki	The Big Prize (IOI17_prize)	C++14	100 / 100	989 ms	900 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
#define vc vector

using namespace std;

int find_best(int n){
    map<int, map<int, int>> pod;
    function<int (int, int)> solve=[&](int l, int r){
        if(l>r) return -1;
        
        int mid=(l+r)/2;
        
        for(auto v: pod){
            int kokvseh=v.first;
            int kokprej=-1, kokpol=-1;
            
            auto pol = v.second.upper_bound( mid);
            if(pol!=v.second.end()) kokpol=(pol->second);
            if(pol!=v.second.begin()) {auto prej = pol;--prej; kokprej=(prej->second);}
            
            
            if(kokpol==0) return -1;
            if(kokprej==kokvseh) return  -1;
            if(kokpol==kokprej) return -1;
        }
        
        vc<int> q=ask(mid);
        
        if(q[0]+q[1]==0) return mid;
        pod[q[0]+q[1]][mid]=q[0];
        
        return max(solve(l, mid-1), solve(mid+1, r));
    };
    return solve(0, n-1);
}

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