| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 293092 | 2020-09-07T16:10:49 Z | luciocf | The Big Prize (IOI17_prize) | C++14 | 96 ms | 2048 KB |
#include <bits/stdc++.h>
#include "prize.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5+10;
pii val[maxn];
pii get(int i)
{
vector<int> v = ask(i);
return {v[0], v[1]};
}
int find_best(int n)
{
for (int i = 0; i < n; i++)
val[i] = {-1, -1};
int ind = 0;
int qtd = 0;
for (int i = 0; i < min(n, 500); i++)
{
pii v = get(i);
if (v.ff+v.ss == 0) return i;
if (v.ff+v.ss >= qtd)
qtd = v.ff+v.ss, ind = i;
}
int ant = ind;
val[ind] = get(ind);
for (int i = 1; i <= 500; i++)
{
int ini = ant+1, fim = n-1, ans;
while (ini <= fim)
{
int mid = (ini+fim)/2;
if (val[mid].ff == -1) val[mid] = get(mid);
if (val[mid].ff+val[mid].ss != qtd)
{
if (val[mid].ff+val[mid].ss == 0) return mid;
ans = mid, fim = mid-1;
}
else if (val[mid].ff-val[ind].ff-(i-1) > 0) fim = mid-1;
else ini = mid+1;
}
ant = ans;
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 1916 KB | Output is correct |
| 2 | Correct | 6 ms | 1920 KB | Output is correct |
| 3 | Correct | 4 ms | 1900 KB | Output is correct |
| 4 | Correct | 4 ms | 1920 KB | Output is correct |
| 5 | Correct | 7 ms | 1920 KB | Output is correct |
| 6 | Correct | 1 ms | 1920 KB | Output is correct |
| 7 | Correct | 4 ms | 1920 KB | Output is correct |
| 8 | Correct | 8 ms | 1912 KB | Output is correct |
| 9 | Correct | 5 ms | 1920 KB | Output is correct |
| 10 | Correct | 4 ms | 1920 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 1920 KB | Output is correct |
| 2 | Correct | 6 ms | 1920 KB | Output is correct |
| 3 | Correct | 4 ms | 1920 KB | Output is correct |
| 4 | Correct | 8 ms | 1912 KB | Output is correct |
| 5 | Correct | 6 ms | 1920 KB | Output is correct |
| 6 | Correct | 1 ms | 1912 KB | Output is correct |
| 7 | Correct | 5 ms | 1920 KB | Output is correct |
| 8 | Correct | 4 ms | 1912 KB | Output is correct |
| 9 | Correct | 5 ms | 1920 KB | Output is correct |
| 10 | Correct | 8 ms | 1824 KB | Output is correct |
| 11 | Correct | 10 ms | 1920 KB | Output is correct |
| 12 | Correct | 8 ms | 1920 KB | Output is correct |
| 13 | Correct | 14 ms | 1920 KB | Output is correct |
| 14 | Correct | 8 ms | 512 KB | Output is correct |
| 15 | Correct | 18 ms | 1916 KB | Output is correct |
| 16 | Partially correct | 60 ms | 1920 KB | Partially correct - number of queries: 6986 |
| 17 | Correct | 4 ms | 1912 KB | Output is correct |
| 18 | Partially correct | 77 ms | 1920 KB | Partially correct - number of queries: 8093 |
| 19 | Correct | 7 ms | 1920 KB | Output is correct |
| 20 | Correct | 22 ms | 1152 KB | Output is correct |
| 21 | Correct | 31 ms | 1920 KB | Output is correct |
| 22 | Correct | 12 ms | 1920 KB | Output is correct |
| 23 | Correct | 6 ms | 1920 KB | Output is correct |
| 24 | Correct | 6 ms | 1920 KB | Output is correct |
| 25 | Correct | 26 ms | 1912 KB | Output is correct |
| 26 | Correct | 48 ms | 1920 KB | Output is correct |
| 27 | Correct | 7 ms | 1920 KB | Output is correct |
| 28 | Partially correct | 65 ms | 1920 KB | Partially correct - number of queries: 7685 |
| 29 | Partially correct | 61 ms | 1912 KB | Partially correct - number of queries: 5943 |
| 30 | Partially correct | 85 ms | 1912 KB | Partially correct - number of queries: 8032 |
| 31 | Correct | 7 ms | 1920 KB | Output is correct |
| 32 | Correct | 8 ms | 1920 KB | Output is correct |
| 33 | Correct | 0 ms | 384 KB | Output is correct |
| 34 | Correct | 33 ms | 1920 KB | Output is correct |
| 35 | Correct | 10 ms | 1920 KB | Output is correct |
| 36 | Correct | 28 ms | 1920 KB | Output is correct |
| 37 | Correct | 7 ms | 1920 KB | Output is correct |
| 38 | Correct | 4 ms | 1896 KB | Output is correct |
| 39 | Correct | 41 ms | 1912 KB | Output is correct |
| 40 | Partially correct | 78 ms | 1920 KB | Partially correct - number of queries: 6941 |
| 41 | Partially correct | 40 ms | 1912 KB | Partially correct - number of queries: 5066 |
| 42 | Partially correct | 31 ms | 1912 KB | Partially correct - number of queries: 5066 |
| 43 | Correct | 40 ms | 1912 KB | Output is correct |
| 44 | Correct | 33 ms | 1912 KB | Output is correct |
| 45 | Correct | 30 ms | 1912 KB | Output is correct |
| 46 | Correct | 7 ms | 2048 KB | Output is correct |
| 47 | Correct | 54 ms | 1920 KB | Output is correct |
| 48 | Partially correct | 49 ms | 1920 KB | Partially correct - number of queries: 6133 |
| 49 | Correct | 11 ms | 1912 KB | Output is correct |
| 50 | Partially correct | 66 ms | 1896 KB | Partially correct - number of queries: 8085 |
| 51 | Correct | 47 ms | 1920 KB | Output is correct |
| 52 | Correct | 5 ms | 1920 KB | Output is correct |
| 53 | Correct | 10 ms | 1920 KB | Output is correct |
| 54 | Correct | 48 ms | 1920 KB | Output is correct |
| 55 | Correct | 7 ms | 1912 KB | Output is correct |
| 56 | Partially correct | 68 ms | 1920 KB | Partially correct - number of queries: 8093 |
| 57 | Partially correct | 55 ms | 1920 KB | Partially correct - number of queries: 6042 |
| 58 | Partially correct | 78 ms | 1920 KB | Partially correct - number of queries: 6110 |
| 59 | Partially correct | 68 ms | 1920 KB | Partially correct - number of queries: 5062 |
| 60 | Correct | 45 ms | 1896 KB | Output is correct |
| 61 | Correct | 10 ms | 1920 KB | Output is correct |
| 62 | Correct | 7 ms | 1920 KB | Output is correct |
| 63 | Correct | 8 ms | 1920 KB | Output is correct |
| 64 | Correct | 8 ms | 1920 KB | Output is correct |
| 65 | Correct | 7 ms | 1920 KB | Output is correct |
| 66 | Correct | 15 ms | 1912 KB | Output is correct |
| 67 | Correct | 7 ms | 1920 KB | Output is correct |
| 68 | Correct | 7 ms | 1920 KB | Output is correct |
| 69 | Correct | 12 ms | 1916 KB | Output is correct |
| 70 | Correct | 8 ms | 1920 KB | Output is correct |
| 71 | Partially correct | 77 ms | 1920 KB | Partially correct - number of queries: 8277 |
| 72 | Correct | 7 ms | 1920 KB | Output is correct |
| 73 | Partially correct | 66 ms | 1920 KB | Partially correct - number of queries: 8149 |
| 74 | Partially correct | 76 ms | 1920 KB | Partially correct - number of queries: 8218 |
| 75 | Correct | 8 ms | 1920 KB | Output is correct |
| 76 | Partially correct | 82 ms | 1920 KB | Partially correct - number of queries: 7126 |
| 77 | Partially correct | 77 ms | 1920 KB | Partially correct - number of queries: 8124 |
| 78 | Correct | 11 ms | 1920 KB | Output is correct |
| 79 | Correct | 39 ms | 1920 KB | Output is correct |
| 80 | Partially correct | 45 ms | 1920 KB | Partially correct - number of queries: 8118 |
| 81 | Partially correct | 93 ms | 1920 KB | Partially correct - number of queries: 7779 |
| 82 | Partially correct | 94 ms | 1920 KB | Partially correct - number of queries: 8067 |
| 83 | Correct | 8 ms | 1920 KB | Output is correct |
| 84 | Partially correct | 75 ms | 1920 KB | Partially correct - number of queries: 6711 |
| 85 | Partially correct | 96 ms | 1920 KB | Partially correct - number of queries: 8088 |
| 86 | Correct | 6 ms | 1920 KB | Output is correct |
| 87 | Correct | 7 ms | 1920 KB | Output is correct |
| 88 | Correct | 7 ms | 1920 KB | Output is correct |
| 89 | Correct | 8 ms | 1920 KB | Output is correct |
| 90 | Correct | 8 ms | 1908 KB | Output is correct |
| 91 | Correct | 4 ms | 1912 KB | Output is correct |
| 92 | Correct | 7 ms | 1920 KB | Output is correct |
| 93 | Correct | 12 ms | 1920 KB | Output is correct |
| 94 | Correct | 6 ms | 1920 KB | Output is correct |
| 95 | Correct | 8 ms | 1920 KB | Output is correct |
| 96 | Correct | 11 ms | 1920 KB | Output is correct |
| 97 | Correct | 6 ms | 1920 KB | Output is correct |