Submission #760026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
760026	2023-06-17T06:53:05 Z	denniskim	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	433 ms	724 KB

lokahia

#include "lokahia.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll chk[210][210];
ll cou[210];
ll grp[210];
ll pa[210], ra[210];
ll cou2[210];

ll ffind(ll here)
{
	if(here == pa[here])
		return pa[here];
	
	return pa[here] = ffind(pa[here]);
}

void uunion(ll X, ll Y)
{
	X = ffind(X);
	Y = ffind(Y);
	
	if(X == Y)
		return;
	
	if(ra[X] < ra[Y])
		pa[X] = Y;
	else if(ra[Y] < ra[X])
		pa[Y] = X;
	
	else
	{
		pa[X] = Y;
		ra[Y]++;
	}
}

ll FindBase(ll N)
{
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<int> dis(0, N - 1);
	
	if(N <= 3)
		return 1;
	
	srand(time(NULL));
	
	if(N <= 17)
	{
		for(ll i = 0 ; i < N ; i++)
		{
			for(ll j = i + 1 ; j < N ; j++)
			{
				ll gap = CollectRelics(i, j);
				
				if(gap != -1)
				{
					grp[i] = gap;
					grp[j] = gap;
				}
			}
		}
		
		for(ll i = 0 ; i < N ; i++)
			cou[grp[i]]++;
		
		ll maxx = 0, ans = 0;
		
		for(ll i = 0 ; i < N ; i++)
		{
			if(maxx < cou[i])
			{
				maxx = cou[i];
				ans = i;
			}
		}
		
		if(maxx * 2 >= N)
			return ans;
		
		return -1;
	}
	
	for(ll i = 0 ; i < N ; i++)
		pa[i] = i, ra[i] = 0, grp[i] = -1;
	
	for(ll i = 0 ; i < 300 - N + 1 ; i++)
	{
		ll num1 = dis(gen), num2 = dis(gen);
		ll coco = 0;
		
		while(chk[ffind(num1)][ffind(num2)] || num1 == num2 || ffind(num1) == ffind(num2))
		{
			num1 = ((rand() * rand() + rand()) % N + N) % N;
			num2 = dis(gen);
			coco++;
			
			if(coco >= 100000)
				break;
		}
		
		if(coco >= 100000)
			continue;
		
		num1 = ffind(num1);
		num2 = ffind(num2);
		
		ll gap = CollectRelics(num1, num2);
		chk[num1][num2] = chk[num2][num1] = 1;
		
		if(gap != -1)
		{
			cou[gap]++;
			grp[num1] = gap;
			grp[num2] = gap;
			grp[gap] = gap;
			pa[num1] = gap;
			pa[num2] = gap;
		}
	}
	
	for(ll i = 0 ; i < N ; i++)
		cou2[ffind(i)]++;
	
	for(ll i = 0 ; i < N ; i++)
	{
		if(cou2[i] > N / 2)
			return i;
	}
	
	ll maxx = 0, sum = 0, ans = 0;
	
	for(ll i = 0 ; i < N ; i++)
	{
		if(cou[i] > maxx)
		{
			maxx = cou[i];
			ans = i;
		}
		
		sum += cou[i];
	}
	
	ll fff = 0;
	ll coco = 0;
	
	for(ll i = 0 ; i < N ; i++)
	{
		if(ans == i)
			coco++;
		
		else if(ffind(i) == ans)
			coco++;
		
		else
		{
			ll gpgp = CollectRelics(i, ans);
			
			if(gpgp == ans)
				coco++;
		}
	}
	
	if(coco > N / 2)
		return ans;
	
	return -1;
}

Compilation message

lokahia.cpp: In function 'll FindBase(ll)':
lokahia.cpp:161:5: warning: unused variable 'fff' [-Wunused-variable]
  161 |  ll fff = 0;
      |     ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Correct : C = 10
2	Correct	1 ms	596 KB	Correct : C = 250
3	Correct	402 ms	656 KB	Correct : C = 91
4	Correct	2 ms	724 KB	Correct : C = 265
5	Incorrect	0 ms	468 KB	Wrong
6	Correct	1 ms	724 KB	Correct : C = 254
7	Correct	1 ms	724 KB	Correct : C = 294
8	Correct	1 ms	596 KB	Correct : C = 250
9	Correct	1 ms	724 KB	Correct : C = 251
10	Correct	1 ms	596 KB	Correct : C = 300
11	Correct	1 ms	596 KB	Correct : C = 246
12	Correct	1 ms	724 KB	Correct : C = 101
13	Correct	1 ms	724 KB	Correct : C = 300
14	Correct	1 ms	724 KB	Correct : C = 250
15	Correct	1 ms	724 KB	Correct : C = 247
16	Correct	1 ms	724 KB	Correct : C = 290
17	Correct	1 ms	724 KB	Correct : C = 300
18	Correct	1 ms	596 KB	Correct : C = 300
19	Correct	1 ms	596 KB	Correct : C = 248
20	Correct	1 ms	724 KB	Correct : C = 267
21	Correct	1 ms	724 KB	Correct : C = 254
22	Correct	1 ms	724 KB	Correct : C = 249
23	Correct	1 ms	724 KB	Correct : C = 262
24	Correct	433 ms	648 KB	Correct : C = 87
25	Correct	1 ms	596 KB	Correct : C = 181
26	Correct	209 ms	648 KB	Correct : C = 144
27	Correct	1 ms	724 KB	Correct : C = 102