Submission #1690912

---

Source Code Expand

import std.stdio, std.conv, std.string, std.container, std.typecons, std.algorithm;

alias Tuple!(int,int) dat;

int AlgoA(int N, int [] A, string S) {
	int cnt = 0;
	foreach(i;S) {
		if(i == 'M') cnt++;
	}
	BinaryHeap!(Array!dat) hq;
	foreach(i;0..cnt) {
		hq.insert(dat(A[i],i));
	}
	int res = 100_000;
	foreach(i;cnt..N) {
		hq.insert(dat(A[i],i));
		while(hq.front()[1] < i-cnt) hq.removeFront();
		res = min(res, hq.front()[0]);
	}
	return res;
}

int AlgoB(int N, int [] A, string S) {
	dat [] tmp;
	foreach(i;0..N) {
		tmp ~= dat(A[i],i);
	}
	auto hq = heapify(tmp);
	while(hq.length()) {
		dat t = hq.front();
		if( (t[1]!=0 && A[t[1]-1] > t[0]) && (t[1] != N-1 && A[t[1]+1] > t[0]) ) {
			A[t[1]] = min(A[t[1]-1], A[t[1]+1]);
		}
		hq.removeFront();
	}
	if(N % 2 == 1) {
		return A[N/2];
	}
	else {
		return max(A[N/2],A[N/2-1]);
	}
}

void main() {
	int N = to!int(readln().chomp());
	int [] A;
	A = readln().chomp().split().to!(int[]);
	string S = readln().chomp();
	int cnt = 0;
	foreach(i;1..(N-1)) {
		if(S[i] != S[i-1]) cnt++;
	}
	if(cnt == 1 && S[0]=='M') {
		writeln(AlgoA(N,A,S));
	}
	else if(cnt == N-2 && S[0]=='M') {
		writeln(AlgoB(N,A,S));
	}
	else {
		writeln("not implemented");
	}
}

Submission Info

Judge Result