oj.uz

Submission #486316

# Submission time Handle Problem Language Result Execution time Memory
486316 2021-11-11T08:34:02 Z NintsiChkhaidze CONSUL (info1cup19_consul) C++14
15.0017 / 100
 51 ms 284 KB 
#include <bits/stdc++.h>
#include "grader.h"
 
using namespace std;
 
int kth(int k);
void say_answer(int k);
int cnt(int k);
 
map <int,int> mp;
 
void solve(int n){    
     if (n<=50){
        mp.clear();
        for (int i = 1; i <= n; i++){
            int val = kth(i);
            mp[val]++;
            if (mp[val] > n/3){
                say_answer(val);
                return;
            }
        }
        say_answer(-1);
        return;
    }
    
    int r=0;
    set <int> st; st.clear();
    for (int i = 1; i <= n; i++){
        int id = rand()%n + 1;
        int val = kth(id);
        if (st.find(val)!=st.end())
            continue;
        r++;
        if (r==60) break;
        
        st.insert(val);
        if (cnt(val) > n/3){
            say_answer(val);
            return;
        }
        r++;
        if (r==60) break;
    }
    
    say_answer(-1);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.001726491 / 65.0

# Verdict Execution time Memory Grader output
1 Partially correct 43 ms 200 KB Output is partially correct
2 Partially correct 44 ms 200 KB Output is partially correct
3 Correct 8 ms 200 KB Output is correct
4 Correct 11 ms 200 KB Output is correct
5 Partially correct 37 ms 200 KB Output is partially correct
6 Partially correct 32 ms 284 KB Output is partially correct
7 Partially correct 49 ms 200 KB Output is partially correct
8 Partially correct 43 ms 200 KB Output is partially correct
9 Partially correct 39 ms 200 KB Output is partially correct
10 Partially correct 51 ms 200 KB Output is partially correct
11 Partially correct 49 ms 200 KB Output is partially correct
12 Partially correct 40 ms 200 KB Output is partially correct
13 Partially correct 48 ms 200 KB Output is partially correct
14 Partially correct 44 ms 200 KB Output is partially correct