Submission #390584

#	Time	Username	Problem	Language	Result	Execution time	Memory
390584		faresbasbs	The Big Prize (IOI17_prize)	C++14	98.85 / 100	80 ms	5252 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<int> p[200001];

vector<int> askk(int pos){
    if(p[pos].size()){
        return p[pos];
    }
    return p[pos] = ask(pos);
}

int find_best(int n){
    int sum = 0;
    for(int i = 0 ; i < 450 ; i += 1){
        int a = rand()%n;
        vector<int> v = askk(a);
        sum = max(sum,v[0]+v[1]);
        if(v[0]+v[1] == 0){
            return a;
        }
    }
    vector<pair<int,vector<int>>> v;
    int p = 0;
    while(p < n){
        while(p < n){
            vector<int> f = askk(p);
            if(f[0]+f[1] == sum){
                v.push_back({p,f});
                break;
            }else{
                if(f[0]+f[1] == 0){
                    return p;
                }
                p += 1;
            }
        }
        p += 512;
    }
    v.push_back({n,{sum,0}});
    for(int i = 0 ; i+1 < v.size() ; i += 1){
        while(v[i+1].second[0] != v[i].second[0]){
            int first = v[i].first , last = v[i+1].first;
            while(last-first > 1){
                int mid = (first+last)/2;
                vector<int> f = askk(mid);
                if(f[0]+f[1] == 0){
                    return mid;
                }
                if(f[0]+f[1] == sum && f[0] == v[i].second[0]){
                    first = mid;
                }else{
                    last = mid;
                }
            }
            if(v[i+1].second[0] == v[i].second[0]+1){
                break;
            }
            vector<int> f;
            for(int j = first+2 ; j < n ; j += 1){
                f = askk(j);
                if(f[0]+f[1] == 0){
                    return j;
                }
                if(f[0]+f[1] == sum){
                    v[i] = {j,f};
                    break;
                }
            }
        }
    }
}

/*int main(){
    cout << find_best(8) << endl;
}*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0 ; i+1 < v.size() ; i += 1){
      |                     ~~~~^~~~~~~~~~
prize.cpp:23:35: warning: control reaches end of non-void function [-Wreturn-type]
   23 |     vector<pair<int,vector<int>>> v;
      |                                   ^

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