oj.uz

Submission #797064

# Submission time Handle Problem Language Result Execution time Memory
797064 2023-07-29T05:41:05 Z Magikarp4000 The Big Prize (IOI17_prize) C++17
90 / 100
 81 ms 5876 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+5, SQRT = 474;
vector<int> a[MAXN];
int sm = -INF, res = -INF;
bool z[MAXN];

void solve(int l, int r) {
    if (l > r) return;
    int mid = (l+r)/2;
    // cout << "l r: " << l << " " << r << ln;
    vector<int> cur = ask(mid-1);
    if (cur[0]+cur[1] == 0) res = mid;
    else if (cur[0]+cur[1] != sm) {
        int j = mid-1;
        vector<int> cur1 = {-1,-1};
        while (j >= l) {
            cur1 = ask(j-1);
            if (cur1[0]+cur1[1] == 0) {
                res = j;
                return;
            }
            else if (cur1[0]+cur1[1] == sm) break;
            j--;
        }
        // if (j == -1) FOR(k,j+1,mid+1) a[k] = {k+1, sm-k};
        if (j < l) FOR(k,j+1,mid+1) a[k] = {a[j][0]+k-j, a[j][1]-max(0,k-j-1)}, z[k] = 1;
        else FOR(k,j,mid+1) a[k] = {cur1[0]+k-j, cur1[1]-max(0,k-j-1)}, z[k] = 1;
        if (!z[mid+1]) {
            vector<int> cur1 = ask(mid);
            if (cur1[0]+cur1[1] == 0) {
                res = mid+1;
                return;
            }
            else if (cur1[0]+cur1[1] != sm) a[mid+1] = {a[mid][0]+1, a[mid][1]-1};
            else a[mid+1] = cur1;
            z[mid+1] = 1;
        }
        if (j >= l && a[j][0]-a[l-1][0] > 0) solve(l,j-1);
        if (a[mid][1]-a[r+1][1] > 1) solve(mid+1,r);
    }
    else {
        a[mid] = cur;
        z[mid] = 1;
        if (!z[mid+1]) {
            vector<int> cur1 = ask(mid);
            if (cur1[0]+cur1[1] == 0) {
                res = mid+1;
                return;
            }
            else if (cur1[0]+cur1[1] != sm) a[mid+1] = {a[mid][0]+1, a[mid][1]-1};
            else a[mid+1] = cur1;
            z[mid+1] = 1;
        }
        if (a[mid][0]-a[l-1][0] > 0) solve(l,mid);
        if (a[mid][1]-a[r+1][1] > 0) solve(mid+1,r);
    }
}

int find_best(int n) {
	FOR(i,0,min(n,SQRT)) a[i] = ask(i);
    FOR(i,0,min(n,SQRT)) {
        sm = max(sm, a[i][0]+a[i][1]);
    }
    // cout << sm << ln;
    a[0] = {0,sm}, a[n+1] = {sm,0};
    z[0] = z[n+1] = 1;
    solve(1,n);
    return res-1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4944 KB Output is correct
2 Correct 5 ms 5012 KB Output is correct
3 Correct 5 ms 5012 KB Output is correct
4 Correct 6 ms 4944 KB Output is correct
5 Correct 4 ms 5012 KB Output is correct
6 Correct 4 ms 5016 KB Output is correct
7 Correct 6 ms 4944 KB Output is correct
8 Correct 6 ms 4944 KB Output is correct
9 Correct 6 ms 4944 KB Output is correct
10 Correct 7 ms 4944 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4944 KB Output is correct
2 Correct 4 ms 5004 KB Output is correct
3 Correct 7 ms 5004 KB Output is correct
4 Correct 5 ms 5016 KB Output is correct
5 Correct 6 ms 4944 KB Output is correct
6 Correct 5 ms 5008 KB Output is correct
7 Correct 6 ms 4944 KB Output is correct
8 Correct 6 ms 4988 KB Output is correct
9 Correct 4 ms 5008 KB Output is correct
10 Correct 7 ms 5072 KB Output is correct
11 Correct 7 ms 5188 KB Output is correct
12 Correct 12 ms 5204 KB Output is correct
13 Correct 9 ms 5120 KB Output is correct
14 Correct 21 ms 5048 KB Output is correct
15 Partially correct 76 ms 5368 KB Partially correct - number of queries: 8200
16 Partially correct 73 ms 5416 KB Partially correct - number of queries: 8673
17 Partially correct 74 ms 5432 KB Partially correct - number of queries: 8592
18 Partially correct 53 ms 5312 KB Partially correct - number of queries: 8603
19 Partially correct 32 ms 5468 KB Partially correct - number of queries: 8185
20 Partially correct 47 ms 5240 KB Partially correct - number of queries: 5824
21 Partially correct 76 ms 5420 KB Partially correct - number of queries: 8591
22 Partially correct 43 ms 5364 KB Partially correct - number of queries: 6713
23 Correct 8 ms 5064 KB Output is correct
24 Correct 14 ms 5120 KB Output is correct
25 Partially correct 51 ms 5296 KB Partially correct - number of queries: 7860
26 Partially correct 43 ms 5412 KB Partially correct - number of queries: 7909
27 Correct 7 ms 4976 KB Output is correct
28 Partially correct 71 ms 5368 KB Partially correct - number of queries: 7822
29 Partially correct 26 ms 5384 KB Partially correct - number of queries: 6746
30 Partially correct 66 ms 5420 KB Partially correct - number of queries: 8591
31 Partially correct 69 ms 5452 KB Partially correct - number of queries: 8585
32 Correct 13 ms 5136 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Partially correct 52 ms 5376 KB Partially correct - number of queries: 8622
35 Correct 5 ms 5072 KB Output is correct
36 Partially correct 43 ms 5328 KB Partially correct - number of queries: 8603
37 Correct 7 ms 5164 KB Output is correct
38 Correct 5 ms 5072 KB Output is correct
39 Partially correct 56 ms 5332 KB Partially correct - number of queries: 8584
40 Partially correct 61 ms 5320 KB Partially correct - number of queries: 7545
41 Partially correct 74 ms 5316 KB Partially correct - number of queries: 8634
42 Partially correct 32 ms 5424 KB Partially correct - number of queries: 8634
43 Partially correct 70 ms 5320 KB Partially correct - number of queries: 8427
44 Partially correct 61 ms 5384 KB Partially correct - number of queries: 8565
45 Partially correct 56 ms 5388 KB Partially correct - number of queries: 7837
46 Partially correct 78 ms 5320 KB Partially correct - number of queries: 8553
47 Partially correct 63 ms 5876 KB Partially correct - number of queries: 7923
48 Partially correct 37 ms 5388 KB Partially correct - number of queries: 8612
49 Partially correct 33 ms 5416 KB Partially correct - number of queries: 8596
50 Partially correct 79 ms 5428 KB Partially correct - number of queries: 8580
51 Partially correct 45 ms 5544 KB Partially correct - number of queries: 8627
52 Partially correct 32 ms 5416 KB Partially correct - number of queries: 8592
53 Correct 7 ms 4996 KB Output is correct
54 Partially correct 62 ms 5396 KB Partially correct - number of queries: 8588
55 Partially correct 60 ms 5456 KB Partially correct - number of queries: 8580
56 Partially correct 72 ms 5376 KB Partially correct - number of queries: 8588
57 Partially correct 32 ms 5512 KB Partially correct - number of queries: 8566
58 Partially correct 69 ms 5504 KB Partially correct - number of queries: 8709
59 Partially correct 58 ms 5424 KB Partially correct - number of queries: 8664
60 Partially correct 77 ms 5372 KB Partially correct - number of queries: 8601
61 Correct 5 ms 5132 KB Output is correct
62 Correct 9 ms 4992 KB Output is correct
63 Correct 6 ms 5072 KB Output is correct
64 Correct 5 ms 5052 KB Output is correct
65 Correct 7 ms 4988 KB Output is correct
66 Correct 12 ms 5028 KB Output is correct
67 Correct 4 ms 4984 KB Output is correct
68 Correct 9 ms 4972 KB Output is correct
69 Correct 9 ms 4944 KB Output is correct
70 Correct 7 ms 4944 KB Output is correct
71 Partially correct 59 ms 5352 KB Partially correct - number of queries: 9048
72 Correct 11 ms 5120 KB Output is correct
73 Partially correct 73 ms 5320 KB Partially correct - number of queries: 8936
74 Partially correct 81 ms 5420 KB Partially correct - number of queries: 8984
75 Correct 9 ms 5052 KB Output is correct
76 Partially correct 72 ms 5344 KB Partially correct - number of queries: 7896
77 Partially correct 50 ms 5516 KB Partially correct - number of queries: 8594
78 Correct 13 ms 5104 KB Output is correct
79 Correct 32 ms 5268 KB Output is correct
80 Partially correct 33 ms 5460 KB Partially correct - number of queries: 8706
81 Partially correct 72 ms 5704 KB Partially correct - number of queries: 8547
82 Partially correct 73 ms 5320 KB Partially correct - number of queries: 8544
83 Correct 7 ms 5072 KB Output is correct
84 Partially correct 51 ms 5304 KB Partially correct - number of queries: 7260
85 Partially correct 56 ms 5368 KB Partially correct - number of queries: 8635
86 Correct 10 ms 5024 KB Output is correct
87 Correct 8 ms 4996 KB Output is correct
88 Correct 10 ms 5040 KB Output is correct
89 Correct 8 ms 4944 KB Output is correct
90 Correct 8 ms 5004 KB Output is correct
91 Correct 7 ms 4996 KB Output is correct
92 Correct 9 ms 4944 KB Output is correct
93 Correct 15 ms 5020 KB Output is correct
94 Correct 15 ms 5072 KB Output is correct
95 Correct 15 ms 5176 KB Output is correct
96 Correct 14 ms 5072 KB Output is correct
97 Correct 5 ms 5036 KB Output is correct