oj.uz

Submission #969105

# Submission time Handle Problem Language Result Execution time Memory
969105 2024-04-24T13:50:41 Z steveonalex CONSUL (info1cup19_consul) C++17
100 / 100
 23 ms 612 KB 
#include <bits/stdc++.h>
#include "grader.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", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

void solve(int n){
    if (n <= 60){
        map<int, int> mp;
        for(int i = 1; i<=n; ++i) mp[kth(i)]++;
        for(pair<int, int> i: mp){
            if (i.second > n / 3) {
                say_answer(i.first);
                return;
            }
        }
    }
    else{
        set<int> S;
        vector<int> perm(n);
        for(int i= 0; i<n; ++i)perm[i] = i + 1;
        shuffle(ALL(perm), rng);

        for(int j= 0, i = 0;j <= 58;++i){
            int x = kth(perm[i]); j++;
            if (S.find(x) == S.end()){
                int y = cnt(x);
                if (y > n / 3) {
                    say_answer(x);
                    return;
                }
                j++;
            }
        }
    }
    say_answer(-1);
}
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     // double rate = 1;
//     // for(int i = 0; i<30; ++i) rate = rate * 2 / 3;

//     // double sigma = 1 - rate;
//     // rate = 1;
//     // for(int i = 0; i<16000; ++i) rate = rate * sigma;
//     // cout << fixed << setprecision(10) << rate << "\n";
 
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 440 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 4 ms 448 KB Output is correct
4 Correct 4 ms 612 KB Output is correct
5 Correct 9 ms 440 KB Output is correct
6 Correct 11 ms 444 KB Output is correct
7 Correct 10 ms 444 KB Output is correct
8 Correct 12 ms 444 KB Output is correct
9 Correct 11 ms 436 KB Output is correct
10 Correct 11 ms 444 KB Output is correct
11 Correct 11 ms 444 KB Output is correct
12 Correct 10 ms 444 KB Output is correct
13 Correct 11 ms 448 KB Output is correct
14 Correct 10 ms 440 KB Output is correct