Submission #148763

#	Time	Username	Problem	Language	Result	Execution time	Memory
148763		TeamSUA (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	8 ms	744 KiB

lokahia

#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

int FindBase(int N){
	int n = N;
	if (n == 1) return 0;
	// if (n <= 17) {
	// 	vector<int> g(n, 0);
	// 	for (int i = 0; i < n; i++) {
	// 		for (int j = 0; j < n; j++) if (i != j) {
	// 			int k = CollectRelics(i, j);
	// 			if (k != -1) {
	// 				g[k] |= (1 << i) | (1 << j);
	// 			}
	// 		}
	// 	}
	// }
	srand(time(NULL));
	int qaq = 298 - n;
	vector<int> f(n, 0);
	for (int i = 1; i <= qaq; i++) {
		int x = rand() % n, y = rand() % n;
		while (x == y) {
			x = rand() % n, y = rand() % n;
		}
		int k = CollectRelics(x, y);
		if (k != -1) f[k]++;
	}
	int u = 0;
	for (int i = 1; i < n; i++)
		if (f[i] > f[u]) u = i;
	int cnt = 0;
	for (int i = 0; i < n; i++) if (i != u) {
		int k = CollectRelics(u, i);
		if (k != -1) cnt++;
	}
	if (cnt >= n / 2) return u;
	return -1;
}

• Subtask 1: 0 / 100