oj.uz

Submission #315025

# Submission time Handle Problem Language Result Execution time Memory
315025 2020-10-22T00:46:47 Z Kevin_Zhang_TW CONSUL (info1cup19_consul) C++17
100 / 100
 43 ms 504 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;
	}
	vector<int> id(n);
	iota(AI(id), 1);
	shuffle(AI(id), gen);
	set<int> did;
	int use = 0;
	for (int x : id) {
		if (use + 2 > lim) break;
		++use;
		int v = kth(x);
		if (did.count(v)) continue;
		did.insert(v);
		if (cnt(v) * 3 > n) {
			say_answer(v);
			return;
		}
		++use;
	}
	say_answer(-1);
	return;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 25 ms 384 KB Output is correct
7 Correct 26 ms 384 KB Output is correct
8 Correct 29 ms 384 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 27 ms 384 KB Output is correct
11 Correct 27 ms 384 KB Output is correct
12 Correct 22 ms 384 KB Output is correct
13 Correct 31 ms 384 KB Output is correct
14 Correct 22 ms 384 KB Output is correct