oj.uz

Submission #961725

# Submission time Handle Problem Language Result Execution time Memory
961725 2024-04-12T11:13:52 Z steveonalex The Big Prize (IOI17_prize) C++17
20 / 100
 48 ms 3628 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 = 450;
        vector<pair<int, int>> b(n, {-1, -1});
        if (n <= 1e4){
            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;
        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 4 ms 2024 KB Output is correct
2 Correct 3 ms 2020 KB Output is correct
3 Correct 4 ms 2016 KB Output is correct
4 Correct 3 ms 2016 KB Output is correct
5 Correct 3 ms 2276 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 3 ms 2020 KB Output is correct
8 Correct 3 ms 2016 KB Output is correct
9 Correct 3 ms 2020 KB Output is correct
10 Correct 4 ms 2024 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2012 KB Output is correct
2 Correct 3 ms 2024 KB Output is correct
3 Correct 3 ms 2016 KB Output is correct
4 Correct 3 ms 2020 KB Output is correct
5 Correct 4 ms 2016 KB Output is correct
6 Correct 3 ms 2024 KB Output is correct
7 Correct 3 ms 2272 KB Output is correct
8 Correct 3 ms 2016 KB Output is correct
9 Correct 3 ms 2016 KB Output is correct
10 Correct 3 ms 2028 KB Output is correct
11 Correct 7 ms 2276 KB Output is correct
12 Correct 5 ms 2300 KB Output is correct
13 Correct 5 ms 2472 KB Output is correct
14 Correct 6 ms 1664 KB Output is correct
15 Correct 25 ms 2664 KB Output is correct
16 Partially correct 24 ms 2688 KB Partially correct - number of queries: 5078
17 Partially correct 26 ms 2836 KB Partially correct - number of queries: 5048
18 Partially correct 36 ms 2632 KB Partially correct - number of queries: 5047
19 Correct 26 ms 2508 KB Output is correct
20 Correct 20 ms 1560 KB Output is correct
21 Partially correct 31 ms 2956 KB Partially correct - number of queries: 5028
22 Correct 17 ms 2624 KB Output is correct
23 Correct 3 ms 2040 KB Output is correct
24 Correct 5 ms 2784 KB Output is correct
25 Correct 27 ms 3184 KB Output is correct
26 Correct 25 ms 2896 KB Output is correct
27 Correct 4 ms 2044 KB Output is correct
28 Correct 29 ms 2608 KB Output is correct
29 Correct 23 ms 2860 KB Output is correct
30 Partially correct 29 ms 3092 KB Partially correct - number of queries: 5038
31 Partially correct 24 ms 2480 KB Partially correct - number of queries: 5048
32 Correct 7 ms 2132 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Partially correct 24 ms 3436 KB Partially correct - number of queries: 5047
35 Correct 4 ms 2040 KB Output is correct
36 Partially correct 26 ms 2664 KB Partially correct - number of queries: 5049
37 Correct 6 ms 2304 KB Output is correct
38 Correct 3 ms 2276 KB Output is correct
39 Partially correct 30 ms 2984 KB Partially correct - number of queries: 5038
40 Correct 26 ms 3084 KB Output is correct
41 Partially correct 31 ms 3156 KB Partially correct - number of queries: 5065
42 Partially correct 28 ms 2888 KB Partially correct - number of queries: 5065
43 Correct 32 ms 2828 KB Output is correct
44 Partially correct 32 ms 2696 KB Partially correct - number of queries: 5052
45 Correct 27 ms 2636 KB Output is correct
46 Partially correct 25 ms 2484 KB Partially correct - number of queries: 5086
47 Correct 29 ms 3148 KB Output is correct
48 Partially correct 32 ms 2804 KB Partially correct - number of queries: 5098
49 Partially correct 28 ms 3128 KB Partially correct - number of queries: 5062
50 Partially correct 26 ms 2876 KB Partially correct - number of queries: 5070
51 Partially correct 28 ms 3628 KB Partially correct - number of queries: 5066
52 Partially correct 25 ms 3372 KB Partially correct - number of queries: 5043
53 Correct 3 ms 2040 KB Output is correct
54 Partially correct 35 ms 3084 KB Partially correct - number of queries: 5037
55 Partially correct 27 ms 3236 KB Partially correct - number of queries: 5067
56 Partially correct 31 ms 3208 KB Partially correct - number of queries: 5086
57 Partially correct 23 ms 2712 KB Partially correct - number of queries: 5025
58 Partially correct 25 ms 2692 KB Partially correct - number of queries: 5051
59 Partially correct 30 ms 3100 KB Partially correct - number of queries: 5067
60 Partially correct 25 ms 2616 KB Partially correct - number of queries: 5025
61 Correct 3 ms 2040 KB Output is correct
62 Correct 4 ms 2040 KB Output is correct
63 Correct 6 ms 2044 KB Output is correct
64 Correct 4 ms 2136 KB Output is correct
65 Correct 4 ms 2016 KB Output is correct
66 Correct 5 ms 2464 KB Output is correct
67 Correct 4 ms 2036 KB Output is correct
68 Correct 3 ms 2020 KB Output is correct
69 Correct 4 ms 2304 KB Output is correct
70 Correct 4 ms 2040 KB Output is correct
71 Partially correct 26 ms 2984 KB Partially correct - number of queries: 5209
72 Correct 5 ms 2560 KB Output is correct
73 Partially correct 29 ms 2972 KB Partially correct - number of queries: 5146
74 Partially correct 27 ms 2568 KB Partially correct - number of queries: 5173
75 Correct 3 ms 2040 KB Output is correct
76 Correct 20 ms 2924 KB Output is correct
77 Partially correct 33 ms 3208 KB Partially correct - number of queries: 5183
78 Correct 4 ms 2272 KB Output is correct
79 Correct 15 ms 2612 KB Output is correct
80 Partially correct 32 ms 2848 KB Partially correct - number of queries: 5155
81 Partially correct 29 ms 3092 KB Partially correct - number of queries: 5189
82 Partially correct 27 ms 2916 KB Partially correct - number of queries: 5089
83 Correct 3 ms 2020 KB Output is correct
84 Correct 27 ms 3104 KB Output is correct
85 Partially correct 29 ms 2928 KB Partially correct - number of queries: 5151
86 Incorrect 48 ms 3244 KB Incorrect
87 Halted 0 ms 0 KB -