oj.uz

Submission #246737

# Submission time Handle Problem Language Result Execution time Memory
246737 2020-07-10T04:32:35 Z SomeoneUnknown CONSUL (info1cup19_consul) C++14
100 / 100
 69 ms 412 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
typedef pair<int, int> ii;

ii mii(int a, int b){
    return make_pair(a,b);
}
void solve(int n)
{
    /// insert your code
    /// for example
    int polls = 50;
    int fchecks = 10;
    vector<int> surveyres;
    if(n <= 60){
        for(int i = 1; i <= n; i++){
            surveyres.push_back(kth(i));
        }
        sort(surveyres.begin(), surveyres.end());
        int prv = 0;
        int amt = 0;
        for(int i = 0; i < n; i++){
            if(prv != surveyres[i]){
                prv = surveyres[i];
                amt = 0;
            }
            ++amt;
            if(amt * 3 > n){
                say_answer(prv);
                return;
            }
        }
        say_answer(-1);
        return;
    }
    priority_queue<ii> best;
    srand(time(0));
    bool touse[n+1];
    for(int i = 0; i <= n; ++i){
        touse[i] = false;
    }
    for(int i = 0; i < polls; i++){
        int x = (rand()%n)+1;
        while(touse[x]){
            x = (rand()%n)+1;
        }
        touse[x] = true;
    }
    for(int i = 0; i <= n; ++i){
        if(touse[i]){
            surveyres.push_back(kth(i));
        }
    }
    sort(surveyres.begin(), surveyres.end());
    for(int i = 1; i < fchecks; i++) best.push(mii(0,0));
    int prv = 0;
    int amt = 0;
    for(int i = 0; i < n; i++){
        if(prv != surveyres[i]){
            best.push(mii(amt, prv));
            prv = surveyres[i];
            amt = 0;
        }
        ++amt;
    }
    best.push(mii(amt,prv));
    for(int i = 0; i < fchecks; i++){
        ii chkng = best.top();
        best.pop();
        if(cnt(chkng.second) * 3 > n){
            say_answer(chkng.second);
            return;
        }
    }
    say_answer(-1);
    return;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 384 KB Output is correct
2 Correct 64 ms 384 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 384 KB Output is correct
2 Correct 54 ms 412 KB Output is correct
3 Correct 56 ms 256 KB Output is correct
4 Correct 49 ms 384 KB Output is correct
5 Correct 69 ms 384 KB Output is correct
6 Correct 53 ms 384 KB Output is correct
7 Correct 57 ms 384 KB Output is correct
8 Correct 62 ms 256 KB Output is correct
9 Correct 68 ms 384 KB Output is correct
10 Correct 65 ms 384 KB Output is correct
11 Correct 55 ms 384 KB Output is correct
12 Correct 46 ms 384 KB Output is correct
13 Correct 57 ms 384 KB Output is correct
14 Correct 62 ms 384 KB Output is correct