oj.uz

Submission #961731

# Submission time Handle Problem Language Result Execution time Memory
961731 2024-04-12T11:29:25 Z steveonalex The Big Prize (IOI17_prize) C++17
97.23 / 100
 40 ms 3672 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 = 500;
        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 / 2; ++i){
            vector<int> cur = ask(i);
            b[i] = {cur[0], cur[1]};
            maximize(ma, cur[0] + cur[1]);
        }
        for(int i = 0; i<BLOCK / 2; ++i){
            vector<int> cur = ask(n-i-1);
            b[n-i-1] = {cur[0], cur[1]};
            maximize(ma, cur[0] + cur[1]);
        }

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

        DnC(BLOCK / 2, n - BLOCK / 2 - 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 3 ms 2012 KB Output is correct
2 Correct 4 ms 2016 KB Output is correct
3 Correct 4 ms 2016 KB Output is correct
4 Correct 3 ms 2020 KB Output is correct
5 Correct 4 ms 2012 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 4 ms 2016 KB Output is correct
8 Correct 3 ms 2024 KB Output is correct
9 Correct 3 ms 2020 KB Output is correct
10 Correct 3 ms 2020 KB Output is correct

Subtask #2
77.23 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2024 KB Output is correct
2 Correct 3 ms 2012 KB Output is correct
3 Correct 3 ms 2016 KB Output is correct
4 Correct 4 ms 2016 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 4 ms 2192 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2020 KB Output is correct
9 Correct 3 ms 2016 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 6 ms 2308 KB Output is correct
12 Correct 6 ms 2300 KB Output is correct
13 Correct 5 ms 2316 KB Output is correct
14 Correct 9 ms 1128 KB Output is correct
15 Correct 29 ms 3124 KB Output is correct
16 Partially correct 27 ms 2948 KB Partially correct - number of queries: 5143
17 Partially correct 25 ms 2960 KB Partially correct - number of queries: 5108
18 Partially correct 24 ms 3204 KB Partially correct - number of queries: 5121
19 Correct 26 ms 2684 KB Output is correct
20 Correct 15 ms 1892 KB Output is correct
21 Partially correct 30 ms 2668 KB Partially correct - number of queries: 5076
22 Correct 28 ms 2312 KB Output is correct
23 Correct 5 ms 2160 KB Output is correct
24 Correct 5 ms 2300 KB Output is correct
25 Correct 40 ms 2436 KB Output is correct
26 Correct 23 ms 3184 KB Output is correct
27 Correct 4 ms 2268 KB Output is correct
28 Correct 28 ms 2620 KB Output is correct
29 Correct 19 ms 2884 KB Output is correct
30 Partially correct 23 ms 2948 KB Partially correct - number of queries: 5096
31 Partially correct 28 ms 2964 KB Partially correct - number of queries: 5076
32 Correct 6 ms 2304 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Partially correct 30 ms 2888 KB Partially correct - number of queries: 5120
35 Correct 5 ms 2040 KB Output is correct
36 Partially correct 25 ms 2672 KB Partially correct - number of queries: 5087
37 Correct 5 ms 2048 KB Output is correct
38 Correct 4 ms 2044 KB Output is correct
39 Partially correct 34 ms 2608 KB Partially correct - number of queries: 5100
40 Correct 31 ms 2692 KB Output is correct
41 Partially correct 34 ms 2984 KB Partially correct - number of queries: 5117
42 Partially correct 29 ms 3208 KB Partially correct - number of queries: 5117
43 Correct 30 ms 2576 KB Output is correct
44 Partially correct 23 ms 2960 KB Partially correct - number of queries: 5135
45 Correct 28 ms 2600 KB Output is correct
46 Partially correct 28 ms 2704 KB Partially correct - number of queries: 5121
47 Correct 26 ms 2900 KB Output is correct
48 Partially correct 24 ms 2708 KB Partially correct - number of queries: 5125
49 Partially correct 21 ms 2948 KB Partially correct - number of queries: 5103
50 Partially correct 27 ms 3128 KB Partially correct - number of queries: 5108
51 Partially correct 23 ms 3180 KB Partially correct - number of queries: 5135
52 Partially correct 25 ms 3672 KB Partially correct - number of queries: 5120
53 Correct 5 ms 2280 KB Output is correct
54 Partially correct 28 ms 2944 KB Partially correct - number of queries: 5110
55 Partially correct 31 ms 2708 KB Partially correct - number of queries: 5127
56 Partially correct 29 ms 2732 KB Partially correct - number of queries: 5123
57 Partially correct 30 ms 2720 KB Partially correct - number of queries: 5109
58 Partially correct 25 ms 3176 KB Partially correct - number of queries: 5135
59 Partially correct 28 ms 2576 KB Partially correct - number of queries: 5119
60 Partially correct 25 ms 2892 KB Partially correct - number of queries: 5062
61 Correct 5 ms 2048 KB Output is correct
62 Correct 3 ms 2044 KB Output is correct
63 Correct 4 ms 2040 KB Output is correct
64 Correct 4 ms 2040 KB Output is correct
65 Correct 3 ms 2024 KB Output is correct
66 Correct 4 ms 2300 KB Output is correct
67 Correct 4 ms 2040 KB Output is correct
68 Correct 4 ms 2048 KB Output is correct
69 Correct 4 ms 2040 KB Output is correct
70 Correct 5 ms 2040 KB Output is correct
71 Partially correct 33 ms 2912 KB Partially correct - number of queries: 5259
72 Correct 5 ms 2048 KB Output is correct
73 Partially correct 26 ms 2944 KB Partially correct - number of queries: 5196
74 Partially correct 33 ms 2400 KB Partially correct - number of queries: 5223
75 Correct 4 ms 2040 KB Output is correct
76 Correct 31 ms 2952 KB Output is correct
77 Partially correct 31 ms 2896 KB Partially correct - number of queries: 5277
78 Correct 6 ms 2272 KB Output is correct
79 Correct 20 ms 2300 KB Output is correct
80 Partially correct 34 ms 2740 KB Partially correct - number of queries: 5262
81 Partially correct 27 ms 3128 KB Partially correct - number of queries: 5233
82 Partially correct 31 ms 2908 KB Partially correct - number of queries: 5175
83 Correct 4 ms 2016 KB Output is correct
84 Correct 25 ms 3112 KB Output is correct
85 Partially correct 24 ms 3300 KB Partially correct - number of queries: 5221
86 Correct 3 ms 2020 KB Output is correct
87 Correct 4 ms 2136 KB Output is correct
88 Correct 3 ms 2012 KB Output is correct
89 Correct 3 ms 2188 KB Output is correct
90 Correct 3 ms 2016 KB Output is correct
91 Correct 4 ms 2012 KB Output is correct
92 Correct 3 ms 2020 KB Output is correct
93 Correct 5 ms 2040 KB Output is correct
94 Correct 5 ms 2300 KB Output is correct
95 Correct 4 ms 2296 KB Output is correct
96 Correct 4 ms 2044 KB Output is correct
97 Correct 3 ms 2016 KB Output is correct