oj.uz

Submission #315022

# Submission time Handle Problem Language Result Execution time Memory
315022 2020-10-22T00:43:53 Z Kevin_Zhang_TW CONSUL (info1cup19_consul) C++17
15 / 100
 43 ms 384 KB 
#include "grader.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;

#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }

int cnt(int x) { return 1; }
void say_answer(int v) { cerr << "Ans is " << v << '\n'; }
int kth(int i) { return 1; }

#else
#define DE(...) 0
#define deubg(...) 0
#endif
const int MAX_N = 300010;

random_device rd;
mt19937 gen(rd());
void solve(int n)
{
	uniform_int_distribution<int> dis(1, n);

	const int lim = min(n, 60);
	if (n <= 50) {
		map<int,int> CT;
		for (int i = 1;i <= n;++i)
			CT[ kth(i) ]++;
		for (auto [a, b] : CT) 
			if (b * 3 > n) {
				say_answer(a);
				return;
			}
		say_answer(-1);
		return;
	}
				
	unordered_set<int> test, did;
	int cur_cnt = 0;
	while (cur_cnt + 2 <= lim && did.size() < n) {
		int id = dis(gen);
		if (did.count(id)) 
			continue;
		did.insert(id);
		int x = kth(id);
		if (test.count(x))
			continue;
		test.insert(x);
		if (cnt(x) > n / 3) {
			say_answer(x);
			return ;
		}
	}
	say_answer(-1);
	return;
}

Compilation message

consul.cpp: In function 'void solve(int)':
consul.cpp:46:42: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |  while (cur_cnt + 2 <= lim && did.size() < n) {
      |                               ~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 256 KB Output is correct

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 384 KB Too many queries
2 Halted 0 ms 0 KB -