oj.uz

Submission #149462

# Submission time Handle Problem Language Result Execution time Memory
149462 2019-09-01T06:32:24 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 7 ms 736 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;
		} else {
			assert(cnt > 0);
			assert(j == N);
			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) {
				if (cur.maxVal == -1) {
					return cur.first;
				} else {
					return cur.maxVal;
				}
			} else {
				return -1;
			}
		}
	}
	return -1;
}

Subtask #1
100.0 / 100.0

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