제출 #149415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149415		USA1 (#200)	로카히아 유적 (FXCUP4_lokahia)	C++17	0 / 100	7 ms	648 KiB

lokahia

#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