oj.uz

답안 #961729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961729 2024-04-12T11:21:27 Z steveonalex 커다란 상품 (IOI17_prize) C++17
97.21 / 100
 38 ms 3920 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 = 520;
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2020 KB Output is correct
2 Correct 3 ms 2020 KB Output is correct
3 Correct 4 ms 2020 KB Output is correct
4 Correct 4 ms 2008 KB Output is correct
5 Correct 3 ms 2020 KB Output is correct
6 Correct 3 ms 2016 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 2268 KB Output is correct

Subtask #2
77.21 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2020 KB Output is correct
2 Correct 3 ms 2012 KB Output is correct
3 Correct 4 ms 2012 KB Output is correct
4 Correct 3 ms 2016 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 3 ms 2020 KB Output is correct
7 Correct 4 ms 2024 KB Output is correct
8 Correct 3 ms 2012 KB Output is correct
9 Correct 4 ms 2020 KB Output is correct
10 Correct 3 ms 2020 KB Output is correct
11 Correct 5 ms 2016 KB Output is correct
12 Correct 6 ms 2528 KB Output is correct
13 Correct 6 ms 2268 KB Output is correct
14 Correct 8 ms 1424 KB Output is correct
15 Correct 27 ms 2688 KB Output is correct
16 Partially correct 26 ms 3168 KB Partially correct - number of queries: 5125
17 Partially correct 38 ms 2600 KB Partially correct - number of queries: 5128
18 Partially correct 30 ms 2896 KB Partially correct - number of queries: 5137
19 Correct 24 ms 3108 KB Output is correct
20 Correct 25 ms 1788 KB Output is correct
21 Partially correct 27 ms 3156 KB Partially correct - number of queries: 5072
22 Correct 24 ms 2880 KB Output is correct
23 Correct 5 ms 2024 KB Output is correct
24 Correct 6 ms 2288 KB Output is correct
25 Correct 26 ms 2928 KB Output is correct
26 Correct 24 ms 3172 KB Output is correct
27 Correct 4 ms 2016 KB Output is correct
28 Correct 25 ms 2844 KB Output is correct
29 Correct 23 ms 2924 KB Output is correct
30 Partially correct 25 ms 2948 KB Partially correct - number of queries: 5123
31 Partially correct 28 ms 2276 KB Partially correct - number of queries: 5105
32 Correct 7 ms 2272 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Partially correct 26 ms 3196 KB Partially correct - number of queries: 5136
35 Correct 4 ms 2268 KB Output is correct
36 Partially correct 21 ms 2732 KB Partially correct - number of queries: 5061
37 Correct 4 ms 2308 KB Output is correct
38 Correct 3 ms 2272 KB Output is correct
39 Partially correct 23 ms 2952 KB Partially correct - number of queries: 5117
40 Correct 24 ms 3136 KB Output is correct
41 Partially correct 25 ms 2940 KB Partially correct - number of queries: 5124
42 Partially correct 27 ms 3372 KB Partially correct - number of queries: 5124
43 Partially correct 30 ms 2680 KB Partially correct - number of queries: 5005
44 Partially correct 32 ms 2828 KB Partially correct - number of queries: 5100
45 Correct 24 ms 2920 KB Output is correct
46 Partially correct 32 ms 2580 KB Partially correct - number of queries: 5151
47 Correct 38 ms 2792 KB Output is correct
48 Partially correct 23 ms 2784 KB Partially correct - number of queries: 5106
49 Partially correct 28 ms 3132 KB Partially correct - number of queries: 5148
50 Partially correct 25 ms 2828 KB Partially correct - number of queries: 5110
51 Partially correct 27 ms 2868 KB Partially correct - number of queries: 5140
52 Partially correct 26 ms 2560 KB Partially correct - number of queries: 5117
53 Correct 6 ms 2272 KB Output is correct
54 Partially correct 23 ms 2872 KB Partially correct - number of queries: 5100
55 Partially correct 34 ms 3176 KB Partially correct - number of queries: 5127
56 Partially correct 33 ms 2608 KB Partially correct - number of queries: 5119
57 Partially correct 27 ms 2844 KB Partially correct - number of queries: 5088
58 Partially correct 29 ms 2480 KB Partially correct - number of queries: 5108
59 Partially correct 26 ms 3388 KB Partially correct - number of queries: 5130
60 Partially correct 29 ms 3660 KB Partially correct - number of queries: 5100
61 Correct 4 ms 2044 KB Output is correct
62 Correct 3 ms 2012 KB Output is correct
63 Correct 3 ms 2272 KB Output is correct
64 Correct 4 ms 2272 KB Output is correct
65 Correct 3 ms 2012 KB Output is correct
66 Correct 7 ms 2320 KB Output is correct
67 Correct 5 ms 2536 KB Output is correct
68 Correct 3 ms 2012 KB Output is correct
69 Correct 6 ms 2452 KB Output is correct
70 Correct 5 ms 2272 KB Output is correct
71 Partially correct 25 ms 2848 KB Partially correct - number of queries: 5279
72 Correct 5 ms 2060 KB Output is correct
73 Partially correct 32 ms 2936 KB Partially correct - number of queries: 5216
74 Partially correct 28 ms 3436 KB Partially correct - number of queries: 5243
75 Correct 4 ms 2020 KB Output is correct
76 Correct 27 ms 2616 KB Output is correct
77 Partially correct 25 ms 3140 KB Partially correct - number of queries: 5275
78 Correct 5 ms 2268 KB Output is correct
79 Correct 13 ms 3088 KB Output is correct
80 Partially correct 32 ms 2844 KB Partially correct - number of queries: 5263
81 Partially correct 27 ms 3384 KB Partially correct - number of queries: 5241
82 Partially correct 27 ms 3420 KB Partially correct - number of queries: 5187
83 Correct 3 ms 2280 KB Output is correct
84 Correct 21 ms 2884 KB Output is correct
85 Partially correct 26 ms 3920 KB Partially correct - number of queries: 5221
86 Correct 3 ms 2016 KB Output is correct
87 Correct 3 ms 2016 KB Output is correct
88 Correct 4 ms 2020 KB Output is correct
89 Correct 3 ms 2020 KB Output is correct
90 Correct 3 ms 2016 KB Output is correct
91 Correct 3 ms 2016 KB Output is correct
92 Correct 4 ms 2020 KB Output is correct
93 Correct 5 ms 2272 KB Output is correct
94 Correct 7 ms 2300 KB Output is correct
95 Correct 4 ms 2272 KB Output is correct
96 Correct 4 ms 2284 KB Output is correct
97 Correct 3 ms 2020 KB Output is correct