oj.uz

Submission #222751

# Submission time Handle Problem Language Result Execution time Memory
222751 2020-04-13T23:35:09 Z achibasadzishvili The Big Prize (IOI17_prize) C++14
90 / 100
 79 ms 3064 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#include "prize.h"
using namespace std;
pair<ll,ll>p , cur , pp[200005];
ll que,fix[200005];
pair<ll,ll> as(ll ind){
    if(fix[ind])return pp[ind];
    fix[ind] = 1;
    vector<ll>v = ask(ind);
    que++;
    pp[ind] = make_pair(v[0] , v[1]);
    return pp[ind];
}
ll find_best(ll n){
    srand(time(NULL));
    ll ind = 0 , mx = 0;
    for(int i=1; i<=500; i++){
        ll t = rand() % n;
        p = as(t);
        if(p.f + p.s > mx){
            mx = p.f + p.s;
            ind = t;
        }
    }
    ll x = ind;
    
    while(x < n){
        p = as(x);
        cur = p;
        if(p.f + p.s == mx){
            ll l = x + 1 , r = n - 1 , mid , nex = x;
            while(r >= l){
                mid = (l + r) / 2;
                p = as(mid);
                if(p.s == cur.s){
                    l = mid + 1;
                    nex = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            x = nex + 1;
        }
        else {
            if(p.f + p.s == 0)return x;
            x++;
        }
    }
    
    x = ind;
    
    while(x >= 0){
        p = as(x);
        cur = p;
        if(p.f + p.s == mx){
            ll l = 0 , r = x - 1 , mid , nex = x;
            while(r >= l){
                mid = (l + r) / 2;
                p = as(mid);
                if(p.f == cur.f){
                    r = mid - 1;
                    nex = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            x = nex - 1;
        }
        else {
            if(p.f + p.s == 0)return x;
            x--;
        }
    }
    
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2176 KB Output is correct
2 Correct 9 ms 2184 KB Output is correct
3 Correct 11 ms 2168 KB Output is correct
4 Correct 13 ms 2176 KB Output is correct
5 Correct 10 ms 2176 KB Output is correct
6 Correct 9 ms 2264 KB Output is correct
7 Correct 13 ms 2168 KB Output is correct
8 Correct 11 ms 2176 KB Output is correct
9 Correct 11 ms 2176 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2176 KB Output is correct
2 Correct 12 ms 2172 KB Output is correct
3 Correct 11 ms 2176 KB Output is correct
4 Correct 11 ms 2176 KB Output is correct
5 Correct 10 ms 2176 KB Output is correct
6 Correct 11 ms 2168 KB Output is correct
7 Correct 11 ms 2368 KB Output is correct
8 Correct 11 ms 2176 KB Output is correct
9 Correct 11 ms 2176 KB Output is correct
10 Correct 11 ms 2176 KB Output is correct
11 Correct 14 ms 2424 KB Output is correct
12 Correct 11 ms 2360 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 23 ms 640 KB Output is correct
15 Partially correct 58 ms 2552 KB Partially correct - number of queries: 6560
16 Correct 23 ms 2296 KB Output is correct
17 Partially correct 51 ms 2748 KB Partially correct - number of queries: 7785
18 Partially correct 49 ms 2552 KB Partially correct - number of queries: 5154
19 Partially correct 75 ms 2680 KB Partially correct - number of queries: 7236
20 Correct 35 ms 1528 KB Output is correct
21 Correct 16 ms 2296 KB Output is correct
22 Partially correct 58 ms 2552 KB Partially correct - number of queries: 5540
23 Correct 10 ms 2240 KB Output is correct
24 Correct 14 ms 2424 KB Output is correct
25 Correct 24 ms 2500 KB Output is correct
26 Correct 34 ms 2564 KB Output is correct
27 Correct 13 ms 2168 KB Output is correct
28 Partially correct 56 ms 2552 KB Partially correct - number of queries: 6602
29 Correct 26 ms 2304 KB Output is correct
30 Correct 26 ms 2376 KB Output is correct
31 Partially correct 64 ms 2656 KB Partially correct - number of queries: 7417
32 Correct 12 ms 2168 KB Output is correct
33 Correct 7 ms 256 KB Output is correct
34 Partially correct 57 ms 2552 KB Partially correct - number of queries: 5921
35 Correct 12 ms 2296 KB Output is correct
36 Partially correct 60 ms 2552 KB Partially correct - number of queries: 6493
37 Correct 15 ms 2424 KB Output is correct
38 Correct 12 ms 2296 KB Output is correct
39 Correct 30 ms 2740 KB Output is correct
40 Correct 19 ms 2296 KB Output is correct
41 Correct 28 ms 2536 KB Output is correct
42 Correct 38 ms 2536 KB Output is correct
43 Correct 40 ms 2552 KB Output is correct
44 Partially correct 39 ms 2516 KB Partially correct - number of queries: 5136
45 Partially correct 56 ms 2552 KB Partially correct - number of queries: 5657
46 Partially correct 66 ms 2680 KB Partially correct - number of queries: 7757
47 Correct 29 ms 2424 KB Output is correct
48 Partially correct 35 ms 2644 KB Partially correct - number of queries: 5168
49 Partially correct 64 ms 2680 KB Partially correct - number of queries: 7632
50 Correct 14 ms 2176 KB Output is correct
51 Partially correct 52 ms 2680 KB Partially correct - number of queries: 5370
52 Partially correct 56 ms 2772 KB Partially correct - number of queries: 7984
53 Correct 11 ms 2176 KB Output is correct
54 Correct 40 ms 2552 KB Output is correct
55 Partially correct 77 ms 2656 KB Partially correct - number of queries: 8267
56 Partially correct 79 ms 2680 KB Partially correct - number of queries: 7829
57 Correct 13 ms 2304 KB Output is correct
58 Correct 12 ms 2304 KB Output is correct
59 Correct 38 ms 2424 KB Output is correct
60 Correct 43 ms 2552 KB Output is correct
61 Correct 11 ms 2040 KB Output is correct
62 Correct 12 ms 2296 KB Output is correct
63 Correct 13 ms 2176 KB Output is correct
64 Correct 11 ms 2168 KB Output is correct
65 Correct 11 ms 2168 KB Output is correct
66 Correct 15 ms 2176 KB Output is correct
67 Correct 18 ms 2168 KB Output is correct
68 Correct 10 ms 2176 KB Output is correct
69 Correct 15 ms 2176 KB Output is correct
70 Correct 10 ms 2168 KB Output is correct
71 Partially correct 69 ms 2680 KB Partially correct - number of queries: 7567
72 Correct 15 ms 2432 KB Output is correct
73 Partially correct 45 ms 2616 KB Partially correct - number of queries: 6910
74 Partially correct 63 ms 2552 KB Partially correct - number of queries: 6944
75 Correct 12 ms 2304 KB Output is correct
76 Partially correct 54 ms 2552 KB Partially correct - number of queries: 5904
77 Partially correct 56 ms 2552 KB Partially correct - number of queries: 6990
78 Correct 13 ms 2432 KB Output is correct
79 Correct 36 ms 2680 KB Output is correct
80 Partially correct 71 ms 2808 KB Partially correct - number of queries: 7995
81 Partially correct 67 ms 2680 KB Partially correct - number of queries: 8021
82 Partially correct 64 ms 2680 KB Partially correct - number of queries: 8027
83 Correct 15 ms 2304 KB Output is correct
84 Partially correct 59 ms 2680 KB Partially correct - number of queries: 6658
85 Partially correct 69 ms 2680 KB Partially correct - number of queries: 8265
86 Partially correct 60 ms 3064 KB Partially correct - number of queries: 6960
87 Correct 15 ms 2304 KB Output is correct
88 Partially correct 60 ms 2688 KB Partially correct - number of queries: 6268
89 Partially correct 63 ms 2680 KB Partially correct - number of queries: 6788
90 Correct 12 ms 2304 KB Output is correct
91 Correct 21 ms 2552 KB Output is correct
92 Partially correct 56 ms 2596 KB Partially correct - number of queries: 6023
93 Partially correct 66 ms 2680 KB Partially correct - number of queries: 7326
94 Partially correct 67 ms 2684 KB Partially correct - number of queries: 7120
95 Partially correct 72 ms 2684 KB Partially correct - number of queries: 7328
96 Partially correct 66 ms 2680 KB Partially correct - number of queries: 6877
97 Partially correct 41 ms 2816 KB Partially correct - number of queries: 6232