oj.uz

Submission #149556

# Submission time Handle Problem Language Result Execution time Memory
149556 2019-09-01T06:43:14 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Lokahian Relics (FXCUP4_lokahia) C++17
39 / 100
 10 ms 720 KB 
#include <bits/stdc++.h>

using namespace std;

#include "lokahia.h"

int FindBase(int N){
	if (N == 1)
		return 0;
	srand(123);
	int left = 600 - (N - 1);
	vector<int> v(N, 1);
	while (left) {
		int hv = N;
		int ta = rand() % hv;
		for (int i = 0; i < N; i++) {
			if (!v[i])
				continue;
			if (ta < v[i]) {
				ta = i;
				hv -= v[i];
				break;
			} else
				ta -= v[i];
		}
		if (!hv)
			break;
		int tb = rand() % hv;
		for (int i = 0; i < N; i++) {
			if (!v[i] || i == ta)
				continue;
			if (tb < v[i]) {
				tb = i;
				hv -= v[i];
				break;
			} else
				tb -= v[i];
		}
		int tc = CollectRelics(ta, tb);
		if (tc != -1) {
			if (tc != ta) {
				v[tc] += v[ta];
				v[ta] = 0;
			}
			if (tc != tb) {
				v[tc] += v[tb];
				v[tb] = 0;
			}
		}
		left--;
	}
	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)
			ma += CollectRelics(i, ans) == ans;
	if (ma > N / 2)
		return ans;
	return -1;
}

Subtask #1
39.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Correct : C = 213
2 Partially correct 6 ms 640 KB Partially correct : C = 600
3 Correct 6 ms 720 KB Correct : C = 210
4 Partially correct 8 ms 640 KB Partially correct : C = 600
5 Partially correct 7 ms 640 KB Partially correct : C = 600
6 Partially correct 6 ms 512 KB Partially correct : C = 600
7 Partially correct 5 ms 640 KB Partially correct : C = 600
8 Partially correct 6 ms 640 KB Partially correct : C = 357
9 Partially correct 6 ms 688 KB Partially correct : C = 600
10 Partially correct 6 ms 512 KB Partially correct : C = 600
11 Partially correct 6 ms 640 KB Partially correct : C = 348
12 Correct 5 ms 512 KB Correct : C = 8
13 Partially correct 7 ms 600 KB Partially correct : C = 600
14 Partially correct 6 ms 640 KB Partially correct : C = 600
15 Partially correct 6 ms 640 KB Partially correct : C = 600
16 Partially correct 10 ms 640 KB Partially correct : C = 600
17 Partially correct 6 ms 640 KB Partially correct : C = 600
18 Partially correct 6 ms 640 KB Partially correct : C = 600
19 Partially correct 7 ms 640 KB Partially correct : C = 600
20 Partially correct 7 ms 640 KB Partially correct : C = 600
21 Partially correct 6 ms 600 KB Partially correct : C = 600
22 Partially correct 6 ms 640 KB Partially correct : C = 600
23 Partially correct 7 ms 600 KB Partially correct : C = 600
24 Partially correct 6 ms 640 KB Partially correct : C = 600
25 Correct 6 ms 512 KB Correct : C = 0
26 Partially correct 8 ms 512 KB Partially correct : C = 600
27 Partially correct 6 ms 640 KB Partially correct : C = 600