oj.uz

Submission #149383

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

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

mt19937_64 rng(94949);
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> cnt(N);
	for(int i=0; i<500-2*N+2; ++i)
	{
		int v1, v2;
		do
		{
			v1 = R(0, N-1);
			v2 = R(0, N-1);
		} while (v1==v2);
		int x = CollectRelics(v1, v2);
		if(x != -1) cnt[x] ++;
	}

	int maxi = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	cnt[maxi] = 0;
	int maxi2 = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	int cc = 1;
	for(int i=0; i<N; ++i)
		if(i != maxi && -1 != CollectRelics(maxi, i))
			++cc;
	if(cc > N/2) return maxi;

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

Subtask #1
51.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 640 KB Partially correct : C = 301
2 Partially correct 6 ms 640 KB Partially correct : C = 301
3 Partially correct 6 ms 640 KB Partially correct : C = 500
4 Correct 6 ms 640 KB Correct : C = 0
5 Partially correct 6 ms 600 KB Partially correct : C = 500
6 Partially correct 6 ms 512 KB Partially correct : C = 500
7 Partially correct 7 ms 560 KB Partially correct : C = 500
8 Partially correct 7 ms 640 KB Partially correct : C = 302
9 Partially correct 6 ms 688 KB Partially correct : C = 500
10 Partially correct 7 ms 640 KB Partially correct : C = 500
11 Partially correct 6 ms 512 KB Partially correct : C = 382
12 Partially correct 6 ms 512 KB Partially correct : C = 381
13 Partially correct 7 ms 688 KB Partially correct : C = 500
14 Partially correct 6 ms 640 KB Partially correct : C = 302
15 Partially correct 6 ms 640 KB Partially correct : C = 302
16 Partially correct 6 ms 640 KB Partially correct : C = 381
17 Partially correct 6 ms 600 KB Partially correct : C = 500
18 Partially correct 6 ms 700 KB Partially correct : C = 301
19 Partially correct 7 ms 640 KB Partially correct : C = 500
20 Partially correct 7 ms 640 KB Partially correct : C = 382
21 Partially correct 6 ms 640 KB Partially correct : C = 381
22 Partially correct 7 ms 640 KB Partially correct : C = 500
23 Partially correct 6 ms 512 KB Partially correct : C = 496
24 Partially correct 6 ms 512 KB Partially correct : C = 382
25 Partially correct 6 ms 720 KB Partially correct : C = 500
26 Partially correct 6 ms 512 KB Partially correct : C = 500
27 Partially correct 6 ms 648 KB Partially correct : C = 500