# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
790673 |
2023-07-23T05:13:07 Z |
ymm |
The Big Prize (IOI17_prize) |
C++17 |
|
1000 ms |
344 KB |
#include "prize.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
jmp_buf jb;
int ans;
const int N = 200'010;
pii table[N];
int n;
pii query(int i) {
if (table[i] != pii{})
return table[i];
auto tmp = ask(i);
if (tmp[0] + tmp[1] == 0) {
ans = i;
longjmp(jb, 1);
}
return (table[i] = {tmp[0], tmp[1]});
}
void solve(int l, int r, int cl, int cr, int tot)
{
if (cl + cr == tot || l >= r)
return;
int m = (l+r)/2;
Loop (i,0,r-l) {
int pos = i%2? m-i/2-1: m+i/2;
auto [x, y] = query(pos);
if (x + y > tot) {
solve(0, n, 0, 0, x + y);
assert(!"unreachable");
}
if (x + y < tot)
continue;
solve(l, pos, cl, y, tot);
solve(pos+1, r, x, cr, tot);
}
}
int find_best(int n) {
::n = n;
if (setjmp(jb))
return ans;
auto [x, y] = query(n/2);
solve(0, n, 0, 0, x+y);
assert(!"unreachable");
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
0 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Execution timed out |
3049 ms |
308 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |