Submission #82287

#	Time	Username	Problem	Language	Result	Execution time	Memory
82287		SecretAgent007	The Big Prize (IOI17_prize)	C++17	100 / 100	56 ms	5496 KiB

prize

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

vector<int> tab[200009];

vector<int> query(int a){
    if(!tab[a].empty()){
        return tab[a];
    }
    return tab[a] = ask(a);
}

int sumQuery(int a){
    return query(a)[0]+query(a)[1];
}

int ans = -1, maxi = 0;

void solve(int l, int r, int nb, int ln){
    if(nb == 0) return;
    if(l > r) return ;
    int a = r-l+1;
    int cnt = 0;
    int start = l;
    int mem = ln;
    for(int i = 1; i <= nb; i++){
        int curr = l+max(1,(r-l+2)/(nb+1))*i-1;
        if(curr >= l && curr <= r){
            if(sumQuery(curr) == 0){
                ans = curr;
                break;
            }
            if(sumQuery(curr) != maxi){
                cnt++;
                continue;
            }
            solve(start, curr-1, query(curr)[0]-mem, mem);
            start = curr+1;
            mem = query(curr)[0];
        }

    }
    if(ans == -1 && cnt  < nb && start <= r){
        solve(start, r, nb-mem+ln, mem);
    }
}

int find_best(int n)
{
    for(int i = 1; i <= 1000; i++){
        int curr = max(1,(n/1000))*i;
        if(curr >= 0 && curr < n){
            if(sumQuery(curr) == 0) return curr;
            maxi = max(maxi, sumQuery(curr));
        }
    }
    int start = 0;
    int ln = 0;
    for(int i = 1; i <= 1000; i++){
        if(ans != -1) return ans;
        int curr = max(1,(n/1000))*i;
        if(curr >= 0 && curr < n && sumQuery(curr) == maxi){
            solve(start, curr-1, query(curr)[0]-ln, ln);
            start = curr+1;
            ln = query(curr)[0];
        }
    }
    if(ans == -1){
        solve(start, n-1, maxi-ln,ln);
    }
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:23:9: warning: unused variable 'a' [-Wunused-variable]
     int a = r-l+1;
         ^

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