oj.uz

Submission #82279

# Submission time Handle Problem Language Result Execution time Memory
82279 2018-10-29T17:38:02 Z SecretAgent007 The Big Prize (IOI17_prize) C++17
20 / 100
 64 ms 5580 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 = l; i <= r; i+=max(1,(nb/a)*a-1)){
        int curr = 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5152 KB Output is correct
2 Correct 15 ms 5152 KB Output is correct
3 Correct 14 ms 5208 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 14 ms 5208 KB Output is correct
6 Correct 16 ms 5208 KB Output is correct
7 Correct 10 ms 5228 KB Output is correct
8 Correct 10 ms 5264 KB Output is correct
9 Correct 17 ms 5264 KB Output is correct
10 Correct 17 ms 5272 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5272 KB Output is correct
2 Correct 12 ms 5332 KB Output is correct
3 Correct 15 ms 5332 KB Output is correct
4 Correct 13 ms 5348 KB Output is correct
5 Correct 10 ms 5348 KB Output is correct
6 Correct 11 ms 5348 KB Output is correct
7 Correct 10 ms 5348 KB Output is correct
8 Correct 11 ms 5348 KB Output is correct
9 Correct 17 ms 5348 KB Output is correct
10 Correct 17 ms 5348 KB Output is correct
11 Correct 27 ms 5368 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Partially correct 64 ms 5436 KB Partially correct - number of queries: 7648
14 Correct 17 ms 5436 KB Output is correct
15 Incorrect 59 ms 5580 KB Incorrect
16 Halted 0 ms 0 KB -