Submission #719359

#	Time	Username	Problem	Language	Result	Execution time	Memory
719359		rainboy	popa (BOI18_popa)	C++17	100 / 100	98 ms	404 KiB

popa

#include "popa.h"

#define N	1000

int qu[N];

int solve(int n, int *ll, int *rr) {
	int cnt, cnt_, h, i;

	cnt = 0;
	for (i = 0; i < n; i++) {
		cnt_ = cnt;
		while (cnt_ && !query(qu[cnt_ - 1], i - 1, qu[cnt_ - 1], i))
			cnt_--;
		if (cnt_ < cnt) {
			ll[i] = qu[cnt_];
			for (h = cnt_; h < cnt; h++)
				rr[qu[h]] = h + 1 < cnt ? qu[h + 1] : -1;
		} else
			ll[i] = -1;
		cnt = cnt_;
		qu[cnt++] = i;
	}
	for (h = 0; h < cnt; h++)
		rr[qu[h]] = h + 1 < cnt ? qu[h + 1] : -1;
	return qu[0];
}

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39