oj.uz

Submission #82273

# Submission time Handle Problem Language Result Execution time Memory
82273 2018-10-29T17:22:49 Z SecretAgent007 The Big Prize (IOI17_prize) C++17
0 / 100
 1000 ms 1025868 KB 
#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 <= a; i++){
        int curr = l+((a)/nb)*i;
        if(curr > r) break;
        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, query(r)[0]-mem, 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){
            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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1106 ms 992368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1139 ms 1025868 KB Time limit exceeded
2 Halted 0 ms 0 KB -