oj.uz

Submission #149415

# Submission time Handle Problem Language Result Execution time Memory
149415 2019-09-01T06:26:24 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 7 ms 648 KB 
#include "lokahia.h"

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

struct f {
	int first;
	int maxVal = -1;
	int cnt = 1;
};

int FindBase(int N){
	vector<f> ranges;
	for (int i = 0; i < N; ) {
		f cur{i};
		int cnt = 1;
		int j;
		for (j = i+1; cnt > 0 && j < N; j++) {
			int v = CollectRelics(i, j);
			if (v == -1) {
				cnt--;
				ranges.push_back(f{j});
			} else {
				cnt++;
				cur.cnt ++;
				cur.maxVal = max(cur.maxVal, v);
			}
		}

		if (cnt == 0) {
			ranges.push_back(cur);
			i = j;
			continue;
		}

		assert(j == N);
		assert(cnt > 0);
		for (const auto& o : ranges) {
			if (o.first > i) {
				// skip it for speed
				continue;
			}
			int v = CollectRelics(i, o.first);
			if (v == -1) {
				// skip it
			} else {
				cur.cnt += o.cnt;
				cur.maxVal = max(cur.maxVal, o.maxVal);
				cur.maxVal = max(cur.maxVal, v);
			}
		}
		if (cur.cnt > N / 2) {
			return cur.maxVal;
		} else {
			return -1;
		}
	}
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Correct : C = 176
2 Correct 6 ms 512 KB Correct : C = 118
3 Correct 6 ms 640 KB Correct : C = 218
4 Correct 7 ms 640 KB Correct : C = 191
5 Correct 6 ms 640 KB Correct : C = 210
6 Correct 6 ms 640 KB Correct : C = 296
7 Correct 6 ms 512 KB Correct : C = 177
8 Correct 7 ms 600 KB Correct : C = 198
9 Correct 6 ms 600 KB Correct : C = 130
10 Correct 6 ms 600 KB Correct : C = 296
11 Correct 7 ms 640 KB Correct : C = 199
12 Correct 6 ms 512 KB Correct : C = 124
13 Correct 6 ms 640 KB Correct : C = 297
14 Correct 6 ms 640 KB Correct : C = 156
15 Correct 6 ms 640 KB Correct : C = 173
16 Correct 7 ms 640 KB Correct : C = 297
17 Correct 5 ms 592 KB Correct : C = 4
18 Correct 7 ms 640 KB Correct : C = 111
19 Correct 7 ms 648 KB Correct : C = 298
20 Correct 5 ms 512 KB Correct : C = 60
21 Correct 6 ms 640 KB Correct : C = 100
22 Incorrect 6 ms 472 KB Wrong
23 Correct 7 ms 640 KB Correct : C = 297
24 Correct 6 ms 600 KB Correct : C = 177
25 Correct 6 ms 512 KB Correct : C = 119
26 Correct 7 ms 600 KB Correct : C = 199
27 Correct 6 ms 640 KB Correct : C = 198