oj.uz

Submission #149451

# Submission time Handle Problem Language Result Execution time Memory
149451 2019-09-01T06:30:57 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 7 ms 768 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; ; ) {
		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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Correct : C = 297
2 Correct 6 ms 512 KB Correct : C = 156
3 Correct 7 ms 640 KB Correct : C = 177
4 Correct 6 ms 640 KB Correct : C = 297
5 Correct 6 ms 640 KB Correct : C = 218
6 Correct 6 ms 512 KB Correct : C = 130
7 Correct 6 ms 640 KB Correct : C = 297
8 Correct 6 ms 640 KB Correct : C = 198
9 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 6 ms 592 KB Correct : C = 210
11 Correct 6 ms 640 KB Correct : C = 124
12 Correct 5 ms 512 KB Correct : C = 0
13 Correct 5 ms 512 KB Correct : C = 118
14 Correct 6 ms 600 KB Correct : C = 119
15 Correct 6 ms 512 KB Correct : C = 173
16 Correct 6 ms 464 KB Correct : C = 4
17 Correct 6 ms 636 KB Correct : C = 296
18 Correct 6 ms 640 KB Correct : C = 176
19 Correct 7 ms 640 KB Correct : C = 296
20 Correct 7 ms 640 KB Correct : C = 199
21 Correct 6 ms 640 KB Correct : C = 298
22 Correct 6 ms 640 KB Correct : C = 198
23 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 6 ms 640 KB Correct : C = 199
27 Correct 6 ms 512 KB Correct : C = 177