Submission #67672005

---

Source Code Expand

#include <stdio.h>

#define KI_MAX (1 << 18)

int ki[KI_MAX * 2 - 1];

int ookikunaihou(int a, int b) {
	return a <= b ? a  : b;
}

void ki_set(int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] = value;
	do {
		pos = (pos - 1) / 2;
		ki[pos] = ookikunaihou(ki[pos * 2 + 1], ki[pos * 2 + 2]);
	} while (pos > 0);
}

int ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return KI_MAX * 2;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_get_i(idx * 2 + 1, ss, sm, qs, qe);
		int r = ki_get_i(idx * 2 + 2, sm, se, qs, qe);
		return ookikunaihou(l, r);
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int N;
int P[KI_MAX];

int first;

void calc(int s, int e) {
	if (s + 1 == e) {
		printf(" %d" + first, P[s]);
		first = 0;
	} else {
		int m = s + (e - s) / 2;
		int left = ki_get(s, m);
		int all = ki_get(s, e);
		if (left == all) {
			/* 前半分に最小の要素がある */
			calc(s, m);
			calc(m, e);
		} else {
			/* 前半分に最小の要素がない → 後ろ半分にある */
			calc(m, e);
			calc(s, m);
		}
	}
}

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int i;
		if (scanf("%d", &N) != 1) return 1;
		for (i = 0; i < (1 << N); i++) {
			if (scanf("%d", &P[i]) != 1) return 1;
			ki_set(i, P[i]);
		}
		first = 1;
		calc(0, 1 << N);
		putchar('\n');
	}
	return 0;
}

/*

より小さい数値があるほうを先に持っていく

*/

Submission Info

Judge Result