Submission #229670

#	Time	Username	Problem	Language	Result	Execution time	Memory
229670		DrSwad	Swap (BOI16_swap)	C++17	100 / 100	101 ms	7544 KiB

swap

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/swad/Desktop/CP/debug.h"
#endif

const int N = int(2e5) + 10;

int n;
int a[N << 1];
int at[N << 1];
int to[N << 1];
int vis[N << 1];

void setVis(int at, int val) {
	if (vis[at]) return;
	vis[at] = val;

	while (at) {
		if (vis[at << 1] == 1) to[at] = to[at << 1];
		else if (vis[at << 1 | 1] != 1) to[at] = at;
		else if (vis[at << 1] == -1) to[at] = to[at << 1 | 1];
		else to[at] = min(to[at << 1], to[at << 1 | 1]);
		at >>= 1;
	}
}

void cancelVis(int from) {
	int at = from;
	while (at < to[from]) {
		if (vis[at << 1] == 1) at <<= 1;
		else if (vis[at << 1] == -1) (at <<= 1) |= 1;
		else {
			if (to[at << 1] < to[at << 1 | 1]) setVis(at << 1, 1), at <<= 1;
			else setVis(at << 1, -1), (at <<= 1) |= 1;
		}
	}
	if (vis[at << 1] != -1) setVis(at << 1, -1);
	if (vis[at << 1 | 1] != -1) setVis(at << 1 | 1, -1);
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		at[a[i]] = i;
	}

	iota(to, to + (N << 1), 0);
	memset(&vis[n + 1], -1, sizeof(int) * ((N << 1) - (n + 1)));

	setVis(1, -1);

	for (int i = 1; i <= n; i++) {
		if (vis[at[i]] != -1) {
			if (at[i] & 1) setVis(at[i], 1);
			else {
				if (vis[at[i] + 1] != 1) setVis(at[i], 1), setVis(at[i] + 1, -1);
				else if (vis[at[i]] == 1) cancelVis(at[i] + 1);
				else {
					if (to[at[i]] < to[at[i] + 1]) {
						cancelVis(at[i]);
						setVis(at[i], -1);
					}
					else {
						cancelVis(at[i] + 1);
						setVis(at[i], 1);
					}
				}
			}
		}
		else cancelVis(at[i]);
	}

	for (int i = 2; i <= n; i++) if (vis[i] == 1) swap(a[i], a[i >> 1]);

	for (int i = 1; i <= n; i++) {
		if (i > 1) printf(" ");
		printf("%d", a[i]);
	}
	puts("");

	return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

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