Submission #96428

#	Time	Username	Problem	Language	Result	Execution time	Memory
96428		ics0503	Swap (BOI16_swap)	C++17	68 / 100	1085 ms	21368 KiB

swap

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[33][221212], n, ck[33][221212],A[33][221212], ADN[33];
void mkA(int dep, int w) {
	if (n < w)return;
	A[dep][ADN[dep]++] = w;
	ck[dep][w] = 0;
	a[dep][w] = a[dep - 1][w];
	mkA(dep, w * 2); mkA(dep, w * 2 + 1);
}
void mkck(int dep, int w) {
	if (n < w)return;
	ck[dep][w] = 1;
	mkck(dep, w * 2); mkck(dep, w * 2 + 1);
}
void cpy(int dep, int w) {
	if (n < w)return;
	a[dep][w] = a[dep + 1][w];
	cpy(dep, w * 2); cpy(dep, w * 2 + 1);
}
int go(int dep, int G, int w) {
	ADN[dep] = 0; mkA(dep, w);
	a[dep][w] = G;
	for (int x = 0; x < ADN[dep]; x++) {
		int now = A[dep][x];
		if (ck[dep][now])continue;
		int l = now * 2, r = now * 2 + 1;
		if (l > n)continue;
		if (r > n){
			if(a[dep][now] > a[dep][l]) swap(a[dep][now], a[dep][l]);
			continue;
		}
		if (a[dep][now] < a[dep][l] && a[dep][now] < a[dep][r])continue;
		else if (a[dep][l] < a[dep][r] && a[dep][l] < a[dep][now])swap(a[dep][now], a[dep][l]);
		else {
			int mn = min(a[dep][l], a[dep][now]);
			int mx = max(a[dep][l], a[dep][now]);
			a[dep][now] = a[dep][r];
			mkck(dep, now);
			int L = go(dep + 1, mn, now * 2), R = go(dep + 1, mn, now * 2 + 1), p, q;
			if (L < R) p = now * 2, q = now * 2 + 1;
			else p = now * 2 + 1, q = now * 2;
			cpy(dep, p);
			go(dep + 1, mx, q); cpy(dep, q);
		}
	}
	for (int x = 0; x < ADN[dep]; x++)if (a[dep][A[dep][x]] == G)return A[dep][x];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[0][i]);
	go(1, a[0][1], 1);
	for (int i = 1; i <= n; i++) printf("%d ", a[1][i]);
	return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int go(int, int, int)':
swap.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:52:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++)scanf("%d", &a[0][i]);
                              ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32