oj.uz

Submission #149742

# Submission time Handle Problem Language Result Execution time Memory
149742 2019-09-01T07:04:12 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 41 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;

#include "lokahia.h"

int FindBase(int N){
	if (N == 1)
		return 0;
	srand(689);
	int left = 300 - N;
	vector<int> v(N, 1);
	map<pair<int, int>, int> m;
	int cnt = 0;
	while (left) {
		int hv = 0;
		for (int i = 0; i < N; i++)
			if (v[i])
				hv += max(20, v[i]);
		int ta = rand() % hv;
		for (int i = 0; i < N; i++) {
			if (!v[i])
				continue;
			if (ta < max(20, v[i])) {
				ta = i;
				hv -= max(20, v[i]);
				break;
			} else
				ta -= max(20, v[i]);
		}
		if (!hv)
			break;
		int tb = rand() % hv;
		for (int i = 0; i < N; i++) {
			if (!v[i] || i == ta)
				continue;
			if (tb < max(20, v[i])) {
				tb = i;
				break;
		} else
				tb -= max(20, v[i]);
		}
		if (ta > tb)
			swap(ta, tb);
		int tc;
		if (m.count({ta, tb})) {
			tc = m[{ta, tb}];
			cnt++;
			if (cnt == 2000) {
				cnt = 0;
				left--;
			}
		} else {
			m[{ta, tb}] = tc = CollectRelics(ta, tb);
			left--;
			cnt = 0;
		}
		if (tc != -1) {
			if (tc != ta) {
				v[tc] += v[ta];
				v[ta] = 0;
			}
			if (tc != tb) {
				v[tc] += v[tb];
				v[tb] = 0;
			}
		}
	}
	int ans = -1, ma = -1;
	for (int i = 0; i < N; i++)
		if (v[i] >= ma) {
			ma = v[i];
			ans = i;
		}
	if (ans == -1)
		return ans;
	ma = 1;
	for (int i = 0; i < N; i++)
		if (i != ans) {
			int ta = CollectRelics(i, ans);
			if (ta == -1)
				continue;
			ma++;
			ans = ta;
		}
	if (ma > N / 2)
		return ans;
	return -1;
}

Subtask #1
100.0 / 100.0

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