oj.uz

Submission #82292

# Submission time Handle Problem Language Result Execution time Memory
82292 2018-10-29T18:59:17 Z SecretAgent007 The Big Prize (IOI17_prize) C++17
0 / 100
 1000 ms 1048576 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 <= nb; i++){
        int curr = l+max(1,(r-l+2)/(nb))*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

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
0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 967 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -