CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1690912

Source codeソースコード

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

Task問題 B - 圧縮 / Compression
User nameユーザ名 047_konjo
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 WA
Score得点 1200
Source lengthソースコード長 1271 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt,sample_4.txt
subtask1 400 / 400 sample_2.txt,subtask_1.2_1.txt,subtask_1.2_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 800 / 800 sample_1.txt,subtask_1.2_1.txt,subtask_1.2_2.txt,subtask_2_1.txt,subtask_2_10.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt
All 0 / 200 sample_1.txt,sample_2.txt,sample_3.txt,sample_4.txt,2_1.txt,2_2.txt,sample_1.txt,sample_2.txt,sample_3.txt,sample_4.txt,subtask_1.2_1.txt,subtask_1.2_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_10.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_10.txt,subtask_3_11.txt,subtask_3_12.txt,subtask_3_13.txt,subtask_3_14.txt,subtask_3_15.txt,subtask_3_16.txt,subtask_3_17.txt,subtask_3_18.txt,subtask_3_19.txt,subtask_3_2.txt,subtask_3_20.txt,subtask_3_21.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
2_1.txt AC 1 ms 256 KB
2_2.txt WA
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt WA
sample_4.txt WA
subtask_1.2_1.txt AC 1 ms 256 KB
subtask_1.2_2.txt AC 1 ms 256 KB
subtask_1_1.txt AC 27 ms 5308 KB
subtask_1_10.txt AC 25 ms 4540 KB
subtask_1_2.txt AC 25 ms 5436 KB
subtask_1_3.txt AC 24 ms 4540 KB
subtask_1_4.txt AC 22 ms 4988 KB
subtask_1_5.txt AC 5 ms 764 KB
subtask_1_6.txt AC 25 ms 4668 KB
subtask_1_7.txt AC 1 ms 256 KB
subtask_1_8.txt AC 26 ms 4924 KB
subtask_1_9.txt AC 25 ms 4540 KB
subtask_2_1.txt AC 113 ms 4156 KB
subtask_2_10.txt AC 113 ms 4412 KB
subtask_2_2.txt AC 113 ms 4412 KB
subtask_2_3.txt AC 113 ms 3900 KB
subtask_2_4.txt AC 115 ms 4412 KB
subtask_2_5.txt AC 1 ms 256 KB
subtask_2_6.txt AC 1 ms 256 KB
subtask_2_7.txt AC 1 ms 256 KB
subtask_2_8.txt AC 111 ms 3908 KB
subtask_2_9.txt AC 25 ms 1276 KB
subtask_3_1.txt WA
subtask_3_10.txt WA
subtask_3_11.txt WA
subtask_3_12.txt WA
subtask_3_13.txt WA
subtask_3_14.txt WA
subtask_3_15.txt WA
subtask_3_16.txt WA
subtask_3_17.txt WA
subtask_3_18.txt WA
subtask_3_19.txt WA
subtask_3_2.txt WA
subtask_3_20.txt WA
subtask_3_21.txt WA
subtask_3_3.txt WA
subtask_3_4.txt WA
subtask_3_5.txt WA
subtask_3_6.txt WA
subtask_3_7.txt WA
subtask_3_8.txt WA
subtask_3_9.txt WA