oj.uz

Submission #149649

# Submission time Handle Problem Language Result Execution time Memory
149649 2019-09-01T06:54:17 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 7 ms 640 KB 
#include "lokahia.h"

#include<bits/stdc++.h>
using namespace std;

mt19937_64 rng(573);
int R(int a, int b)
{
	return uniform_int_distribution<int>(a, b)(rng);
}

int FindBase(int N){
	if(N==1) return 0;
	
	vector<int> x;
	for(int i=0; i<N; ++i) x.push_back(i);

	shuffle(x.begin(), x.end(), rng);

	vector<int> cnt(N);

	for(int i=0; i<N/2; ++i)
	{
		int v1 = x[2*i];
		int v2 = x[2*i+1];
		int y = CollectRelics(v1, v2);
		//printf("%d %d %d\n", v1, v2, y);
		if(y != -1) cnt[y] ++;
	}
	if(N%2==1) cnt[x[N-1]]++;
	int maxi = max_element(cnt.begin(), cnt.end()) - cnt.begin();

	if(cnt[maxi] == 0) return -1;

	int cc = 1;
	for(int i=0; i<N; ++i)
		if(i != maxi && -1 != CollectRelics(maxi, i))
			++cc;
	if(cc > N/2) return maxi;
	return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Correct : C = 177
2 Correct 6 ms 640 KB Correct : C = 299
3 Correct 6 ms 640 KB Correct : C = 179
4 Correct 7 ms 640 KB Correct : C = 299
5 Correct 6 ms 512 KB Correct : C = 0
6 Correct 6 ms 640 KB Correct : C = 297
7 Correct 6 ms 640 KB Correct : C = 299
8 Correct 6 ms 600 KB Correct : C = 179
9 Correct 7 ms 640 KB Correct : C = 299
10 Correct 6 ms 640 KB Correct : C = 297
11 Correct 7 ms 512 KB Correct : C = 177
12 Correct 6 ms 640 KB Correct : C = 297
13 Correct 5 ms 512 KB Correct : C = 177
14 Correct 6 ms 640 KB Correct : C = 299
15 Correct 7 ms 640 KB Correct : C = 299
16 Correct 6 ms 640 KB Correct : C = 297
17 Correct 6 ms 640 KB Correct : C = 297
18 Correct 5 ms 640 KB Correct : C = 297
19 Correct 6 ms 600 KB Correct : C = 177
20 Correct 6 ms 640 KB Correct : C = 299
21 Correct 6 ms 512 KB Correct : C = 179
22 Correct 6 ms 640 KB Correct : C = 100
23 Correct 5 ms 512 KB Correct : C = 177
24 Correct 5 ms 512 KB Correct : C = 6
25 Correct 6 ms 600 KB Correct : C = 297
26 Correct 6 ms 640 KB Correct : C = 179
27 Correct 6 ms 512 KB Correct : C = 60