| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 232826 | 2020-05-18T10:07:56 Z | cfalas | The Big Prize (IOI17_prize) | C++14 | 343 ms | 472108 KB |
#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
#define MID ((l+r)/2)
typedef vector<int> vi;
typedef pair<int, int> ii;
#define F first
#define S second
ii mem[1000000];
bool used[1000000];
set<int> s[10000000];
ii q(int x){
if(used[x]) return mem[x];
used[x] = true;
vi a = ask(x);
mem[x] = ii(a[0],a[1]);
return mem[x];
}
int N;
int mina=0;
int rec(int l=0, int r=N-1){
if(l>r) return -1;
ii a = q(MID);
if(a.F+a.S==0) return MID;
int tot = a.F+a.S;
auto it = s[a.F+a.S].insert(MID).F;
if(it==s[tot].begin() || mem[*prev(it)] != mem[MID]){
int b = rec(l,MID-1);
if(b!=-1) return b;
}
if(it==--s[tot].end() || mem[*next(it)] != mem[MID]){
int b = rec(MID+1,r);
if(b!=-1) return b;
}
return -1;
}
int find_best(int n) {
N = n;
int l=0, r=n-1;
int m;
int pos=0;
return rec();
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 289 ms | 470008 KB | Output is correct |
| 2 | Correct | 285 ms | 470264 KB | Output is correct |
| 3 | Correct | 291 ms | 470136 KB | Output is correct |
| 4 | Correct | 298 ms | 470040 KB | Output is correct |
| 5 | Correct | 281 ms | 470136 KB | Output is correct |
| 6 | Correct | 289 ms | 470008 KB | Output is correct |
| 7 | Correct | 280 ms | 470136 KB | Output is correct |
| 8 | Correct | 292 ms | 470140 KB | Output is correct |
| 9 | Correct | 283 ms | 470008 KB | Output is correct |
| 10 | Correct | 282 ms | 470136 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 277 ms | 470136 KB | Output is correct |
| 2 | Correct | 289 ms | 470172 KB | Output is correct |
| 3 | Correct | 293 ms | 470144 KB | Output is correct |
| 4 | Correct | 286 ms | 470388 KB | Output is correct |
| 5 | Correct | 279 ms | 470136 KB | Output is correct |
| 6 | Correct | 281 ms | 470136 KB | Output is correct |
| 7 | Correct | 281 ms | 470212 KB | Output is correct |
| 8 | Correct | 278 ms | 470136 KB | Output is correct |
| 9 | Correct | 278 ms | 470136 KB | Output is correct |
| 10 | Correct | 278 ms | 470140 KB | Output is correct |
| 11 | Correct | 282 ms | 470392 KB | Output is correct |
| 12 | Correct | 274 ms | 470008 KB | Output is correct |
| 13 | Correct | 324 ms | 470904 KB | Output is correct |
| 14 | Correct | 284 ms | 470036 KB | Output is correct |
| 15 | Correct | 284 ms | 470392 KB | Output is correct |
| 16 | Correct | 326 ms | 471672 KB | Output is correct |
| 17 | Correct | 289 ms | 470128 KB | Output is correct |
| 18 | Correct | 343 ms | 471928 KB | Output is correct |
| 19 | Correct | 285 ms | 470136 KB | Output is correct |
| 20 | Correct | 305 ms | 470392 KB | Output is correct |
| 21 | Correct | 300 ms | 470904 KB | Output is correct |
| 22 | Correct | 280 ms | 470264 KB | Output is correct |
| 23 | Correct | 275 ms | 470008 KB | Output is correct |
| 24 | Correct | 290 ms | 470136 KB | Output is correct |
| 25 | Correct | 307 ms | 471012 KB | Output is correct |
| 26 | Correct | 303 ms | 471096 KB | Output is correct |
| 27 | Correct | 285 ms | 470136 KB | Output is correct |
| 28 | Correct | 315 ms | 471800 KB | Output is correct |
| 29 | Correct | 307 ms | 471672 KB | Output is correct |
| 30 | Correct | 317 ms | 472056 KB | Output is correct |
| 31 | Correct | 286 ms | 470112 KB | Output is correct |
| 32 | Correct | 284 ms | 470624 KB | Output is correct |
| 33 | Correct | 305 ms | 470008 KB | Output is correct |
| 34 | Correct | 302 ms | 470624 KB | Output is correct |
| 35 | Correct | 306 ms | 470392 KB | Output is correct |
| 36 | Correct | 297 ms | 470424 KB | Output is correct |
| 37 | Correct | 290 ms | 470136 KB | Output is correct |
| 38 | Correct | 279 ms | 470136 KB | Output is correct |
| 39 | Correct | 298 ms | 470952 KB | Output is correct |
| 40 | Correct | 317 ms | 471932 KB | Output is correct |
| 41 | Correct | 306 ms | 471236 KB | Output is correct |
| 42 | Correct | 307 ms | 471164 KB | Output is correct |
| 43 | Correct | 300 ms | 471160 KB | Output is correct |
| 44 | Correct | 301 ms | 470776 KB | Output is correct |
| 45 | Correct | 295 ms | 470652 KB | Output is correct |
| 46 | Correct | 278 ms | 470264 KB | Output is correct |
| 47 | Correct | 295 ms | 470776 KB | Output is correct |
| 48 | Correct | 312 ms | 471544 KB | Output is correct |
| 49 | Correct | 296 ms | 470136 KB | Output is correct |
| 50 | Correct | 319 ms | 471892 KB | Output is correct |
| 51 | Correct | 298 ms | 470776 KB | Output is correct |
| 52 | Correct | 269 ms | 470008 KB | Output is correct |
| 53 | Correct | 277 ms | 470392 KB | Output is correct |
| 54 | Correct | 290 ms | 470904 KB | Output is correct |
| 55 | Correct | 282 ms | 470156 KB | Output is correct |
| 56 | Correct | 343 ms | 471928 KB | Output is correct |
| 57 | Correct | 323 ms | 471416 KB | Output is correct |
| 58 | Correct | 315 ms | 471416 KB | Output is correct |
| 59 | Correct | 306 ms | 471160 KB | Output is correct |
| 60 | Correct | 310 ms | 471160 KB | Output is correct |
| 61 | Correct | 286 ms | 470392 KB | Output is correct |
| 62 | Correct | 274 ms | 470008 KB | Output is correct |
| 63 | Correct | 286 ms | 470392 KB | Output is correct |
| 64 | Correct | 309 ms | 470380 KB | Output is correct |
| 65 | Correct | 274 ms | 470136 KB | Output is correct |
| 66 | Correct | 276 ms | 470136 KB | Output is correct |
| 67 | Correct | 270 ms | 470136 KB | Output is correct |
| 68 | Correct | 276 ms | 470008 KB | Output is correct |
| 69 | Correct | 274 ms | 470136 KB | Output is correct |
| 70 | Correct | 276 ms | 470136 KB | Output is correct |
| 71 | Correct | 312 ms | 472108 KB | Output is correct |
| 72 | Correct | 281 ms | 470776 KB | Output is correct |
| 73 | Correct | 310 ms | 472056 KB | Output is correct |
| 74 | Correct | 304 ms | 472064 KB | Output is correct |
| 75 | Correct | 272 ms | 470392 KB | Output is correct |
| 76 | Correct | 316 ms | 471928 KB | Output is correct |
| 77 | Correct | 327 ms | 471928 KB | Output is correct |
| 78 | Correct | 278 ms | 470904 KB | Output is correct |
| 79 | Correct | 292 ms | 471800 KB | Output is correct |
| 80 | Correct | 301 ms | 472056 KB | Output is correct |
| 81 | Correct | 319 ms | 471928 KB | Output is correct |
| 82 | Correct | 323 ms | 472056 KB | Output is correct |
| 83 | Correct | 275 ms | 470264 KB | Output is correct |
| 84 | Correct | 302 ms | 472040 KB | Output is correct |
| 85 | Correct | 311 ms | 472056 KB | Output is correct |
| 86 | Correct | 285 ms | 470776 KB | Output is correct |
| 87 | Correct | 282 ms | 470520 KB | Output is correct |
| 88 | Correct | 273 ms | 470904 KB | Output is correct |
| 89 | Correct | 278 ms | 470648 KB | Output is correct |
| 90 | Correct | 274 ms | 470332 KB | Output is correct |
| 91 | Correct | 277 ms | 470392 KB | Output is correct |
| 92 | Correct | 274 ms | 470136 KB | Output is correct |
| 93 | Correct | 281 ms | 470520 KB | Output is correct |
| 94 | Correct | 277 ms | 470648 KB | Output is correct |
| 95 | Correct | 279 ms | 470648 KB | Output is correct |
| 96 | Correct | 273 ms | 470520 KB | Output is correct |
| 97 | Correct | 279 ms | 470136 KB | Output is correct |