oj.uz

Submission #961728

# Submission time Handle Problem Language Result Execution time Memory
961728 2024-04-12T11:19:29 Z steveonalex The Big Prize (IOI17_prize) C++17
97.61 / 100
 31 ms 3952 KB 
#include <bits/stdc++.h>
#include "prize.h"

 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n"){
        for(auto i: a) cout << i << separator;
        cout << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
// namespace Interactor{
//     const int BLOCK = 400;
//     int n;
//     vector<int> a;

//     vector<int> ask(int i){
//         vector<int> ans(2);
//         for(int j = 0; j < i; ++j) ans[0] += (a[j] < a[i]);
//         for(int j = i+1; j<n; ++j) ans[1] += (a[j] < a[i]);
//         return ans;
//     }

    int range_query(set<int> &S, int l, int r){
        auto it = S.lower_bound(l);
        int cnt = 0;
        while(it != S.end()){
            if (*it > r) break;
            cnt++;
            it++;
        }
        return cnt;
    }

    void DnC(int l, int r, int ma, vector<pair<int, int>> &b, set<int> &S1, set<int> &S2){
        if (l > r) return;
        int x = (l + r) >> 1;
        if (b[x].first == -1){
            vector<int> cur= ask(x);
            b[x] = {cur[0], cur[1]};
        }
        if (b[x].first + b[x].second == ma){
            S1.insert(x);

            // look to the left
            auto it = S1.lower_bound(x); it--;
            int dL = b[x].first - b[*it].first;
            if (dL - range_query(S2, *it, x) > 0) DnC(l, x - 1, ma, b, S1, S2);

            // look to the right
            it = S1.upper_bound(x);
            if (it == S1.end()) {
                DnC(x + 1, r, ma, b, S1, S2);
                return;
            }
            dL = b[*it].first - b[x].first;
            if (dL - range_query(S2, x, *it) > 0) DnC(x + 1, r, ma, b, S1, S2);
        }
        else{
            S2.insert(x);
            DnC(l, x - 1, ma, b, S1, S2);
            DnC(x + 1, r, ma, b, S1, S2);
        }
    }

    int find_best(int n) {
        const int BLOCK = 480;
        vector<pair<int, int>> b(n, {-1, -1});
        if (n <= 5000){
            for(int i = 0; i<n; ++i) {
                vector<int> cur = ask(i);
                if (cur[0] + cur[1] == 0) return i;
            }
        }
        int ma = 0;
        for(int i = 0; i<BLOCK; ++i){
            vector<int> cur = ask(i);
            b[i] = {cur[0], cur[1]};
            maximize(ma, cur[0] + cur[1]);
        }

        set<int> S1, S2;
        for(int i = 0; i<BLOCK; ++i){
            if (b[i].first + b[i].second == ma) S1.insert(i);
            else S2.insert(i);
        }

        DnC(BLOCK, n-1, ma, b, S1, S2);


        for(int i: S2) if (b[i].first + b[i].second == 0) return i;
        exit(-1);
        return -1;
    }

//     bool solve(){
//         n = 2e5;
//         a.resize(n, 3);
//         a[0] = 1;
//         for(int i = 1; i<=BLOCK; ++i) a[i] = 2;
//         // reverse(ALL(a));
//         shuffle(ALL(a), rng);

//         // printArr(a, "");

//         int j = find_best(n);
//         cout << "! " << j << "\n";
//         return a[j] == 1; 
//     }

// }

 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     bool verdict = Interactor::solve();
//     if (verdict) cout << "AC\n";
//     else cout << "WA\n";

//     return 0;
// }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2020 KB Output is correct
2 Correct 3 ms 2016 KB Output is correct
3 Correct 3 ms 2016 KB Output is correct
4 Correct 4 ms 2016 KB Output is correct
5 Correct 4 ms 2016 KB Output is correct
6 Correct 3 ms 2020 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2024 KB Output is correct
9 Correct 3 ms 2016 KB Output is correct
10 Correct 3 ms 2016 KB Output is correct

Subtask #2
77.61 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2020 KB Output is correct
2 Correct 3 ms 2012 KB Output is correct
3 Correct 3 ms 2016 KB Output is correct
4 Correct 3 ms 2024 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 3 ms 2020 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2008 KB Output is correct
9 Correct 3 ms 2012 KB Output is correct
10 Correct 3 ms 2016 KB Output is correct
11 Correct 5 ms 2448 KB Output is correct
12 Correct 5 ms 2548 KB Output is correct
13 Correct 4 ms 2040 KB Output is correct
14 Correct 7 ms 876 KB Output is correct
15 Correct 26 ms 2948 KB Output is correct
16 Partially correct 31 ms 2016 KB Partially correct - number of queries: 5088
17 Partially correct 27 ms 2560 KB Partially correct - number of queries: 5099
18 Partially correct 27 ms 3952 KB Partially correct - number of queries: 5110
19 Correct 31 ms 2924 KB Output is correct
20 Correct 16 ms 1592 KB Output is correct
21 Partially correct 23 ms 2920 KB Partially correct - number of queries: 5059
22 Correct 21 ms 2584 KB Output is correct
23 Correct 4 ms 2040 KB Output is correct
24 Correct 5 ms 2048 KB Output is correct
25 Correct 26 ms 2848 KB Output is correct
26 Correct 23 ms 2904 KB Output is correct
27 Correct 4 ms 2272 KB Output is correct
28 Correct 21 ms 2596 KB Output is correct
29 Correct 18 ms 2324 KB Output is correct
30 Partially correct 22 ms 2412 KB Partially correct - number of queries: 5075
31 Partially correct 28 ms 2900 KB Partially correct - number of queries: 5071
32 Correct 5 ms 2300 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Partially correct 29 ms 2912 KB Partially correct - number of queries: 5089
35 Correct 3 ms 2292 KB Output is correct
36 Partially correct 23 ms 3444 KB Partially correct - number of queries: 5099
37 Correct 6 ms 2016 KB Output is correct
38 Correct 4 ms 2040 KB Output is correct
39 Partially correct 28 ms 3608 KB Partially correct - number of queries: 5056
40 Correct 24 ms 3612 KB Output is correct
41 Partially correct 25 ms 3392 KB Partially correct - number of queries: 5105
42 Partially correct 26 ms 3072 KB Partially correct - number of queries: 5105
43 Correct 26 ms 3172 KB Output is correct
44 Partially correct 27 ms 2920 KB Partially correct - number of queries: 5056
45 Correct 24 ms 2680 KB Output is correct
46 Partially correct 20 ms 3080 KB Partially correct - number of queries: 5076
47 Correct 20 ms 2908 KB Output is correct
48 Partially correct 26 ms 3120 KB Partially correct - number of queries: 5107
49 Partially correct 26 ms 2628 KB Partially correct - number of queries: 5086
50 Partially correct 26 ms 3348 KB Partially correct - number of queries: 5070
51 Partially correct 26 ms 3184 KB Partially correct - number of queries: 5102
52 Partially correct 30 ms 2624 KB Partially correct - number of queries: 5099
53 Correct 3 ms 2048 KB Output is correct
54 Partially correct 26 ms 2828 KB Partially correct - number of queries: 5037
55 Partially correct 29 ms 2660 KB Partially correct - number of queries: 5117
56 Partially correct 23 ms 3712 KB Partially correct - number of queries: 5109
57 Partially correct 27 ms 3128 KB Partially correct - number of queries: 5057
58 Partially correct 31 ms 2896 KB Partially correct - number of queries: 5108
59 Partially correct 29 ms 3440 KB Partially correct - number of queries: 5102
60 Partially correct 24 ms 2980 KB Partially correct - number of queries: 5058
61 Correct 4 ms 2040 KB Output is correct
62 Correct 4 ms 2048 KB Output is correct
63 Correct 4 ms 2040 KB Output is correct
64 Correct 4 ms 2012 KB Output is correct
65 Correct 3 ms 2016 KB Output is correct
66 Correct 9 ms 2132 KB Output is correct
67 Correct 5 ms 2300 KB Output is correct
68 Correct 3 ms 2016 KB Output is correct
69 Correct 5 ms 2300 KB Output is correct
70 Correct 4 ms 2296 KB Output is correct
71 Partially correct 27 ms 3108 KB Partially correct - number of queries: 5239
72 Correct 4 ms 2056 KB Output is correct
73 Partially correct 27 ms 2984 KB Partially correct - number of queries: 5176
74 Partially correct 31 ms 2392 KB Partially correct - number of queries: 5203
75 Correct 5 ms 2048 KB Output is correct
76 Correct 26 ms 2672 KB Output is correct
77 Partially correct 20 ms 3136 KB Partially correct - number of queries: 5202
78 Correct 6 ms 2528 KB Output is correct
79 Correct 19 ms 2292 KB Output is correct
80 Partially correct 23 ms 3868 KB Partially correct - number of queries: 5217
81 Partially correct 27 ms 2524 KB Partially correct - number of queries: 5168
82 Partially correct 24 ms 2852 KB Partially correct - number of queries: 5173
83 Correct 3 ms 2020 KB Output is correct
84 Correct 23 ms 2852 KB Output is correct
85 Partially correct 22 ms 3064 KB Partially correct - number of queries: 5175
86 Correct 3 ms 2016 KB Output is correct
87 Correct 3 ms 2012 KB Output is correct
88 Correct 3 ms 2020 KB Output is correct
89 Correct 3 ms 2020 KB Output is correct
90 Correct 3 ms 2020 KB Output is correct
91 Correct 3 ms 2020 KB Output is correct
92 Correct 3 ms 2016 KB Output is correct
93 Correct 4 ms 2296 KB Output is correct
94 Correct 4 ms 2300 KB Output is correct
95 Correct 5 ms 2300 KB Output is correct
96 Correct 5 ms 2044 KB Output is correct
97 Correct 4 ms 2016 KB Output is correct