Submission #138470

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138470	2019-07-30T05:01:50 Z	임유진(#3321)	Non-boring sequences (CERC12_D)	C++14	0 / 1	145 ms	1092 KB

D

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

const int MAXN = 200005;

int A[MAXN];
int nx[MAXN], pv[MAXN];
int as[MAXN];
int idx[MAXN];

bool boring(int s, int e) {
	priority_queue<int> mx, mxt;
	priority_queue<int, vector<int>, greater<int> > mn, mnt;
	
	//printf("boring(%d, %d)\n", s, e);
	for(int i = s; i <= e; i++) if(pv[i] < s && nx[i] > e) {
		mx.push(i);
		mn.push(i);
	}
	while(!mx.empty()) {
		if(mn.top() - s < e - mx.top()) {
			int t = mn.top();
			mn.pop();
			mxt.push(t);
			for(int i = s; i < t; i++) if(nx[i] <= e && nx[nx[i]] > e) {
				mn.push(nx[i]);
				mx.push(nx[i]);
			}
			if(boring(s, t - 1)) return true;
			s = t + 1;
		}
		else {
			int t = mx.top();
			mx.pop();
			mnt.push(t);
			for(int i = t + 1; i <= e; i++) if(pv[i] >= s && pv[pv[i]] < s) {
				mn.push(pv[i]);
				mx.push(pv[i]);
			}
			if(boring(t + 1, e)) return true;
			e = t - 1;
		}
		while(!mxt.empty() && mx.top() == mxt.top()) {
			mx.pop();
			mxt.pop();
		}
		while(!mnt.empty() && mn.top() == mnt.top()) {
			mn.pop();
			mnt.pop();
		}
	}
	return s <= e;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T;
	
	cin >> T;
	while(T--) {
		//printf("*\n");
		int N;
		cin >> N;
		for(int i = 0; i < N; i++) cin >> A[i];
		for(int i = 0; i < N; i++) as[i] = A[i];
		sort(as, as + N);
		for(int i = 0; i < N; i++) A[i] = lower_bound(as, as + N, A[i]) - as;
		for(int i = 0; i < N; i++) {
			idx[i] = -1;
			nx[i] = N;
		}
		for(int i = 0; i < N; i++) {
			if(idx[A[i]] != -1) nx[idx[A[i]]] = i;
			pv[i] = idx[A[i]];
			idx[A[i]] = i;
		}
		//for(int i = 0; i < N; i++) printf("(%d, %d) ", pv[i], nx[i]);
		//printf("\n");
		if(boring(0, N - 1)) cout << "boring\n";
		else cout << "non-boring\n";
	}
	return 0;
}

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	145 ms	1092 KB	Output isn't correct
2	Halted	0 ms	0 KB	-