Submission #56899

#	Time	Username	Problem	Language	Result	Execution time	Memory
56899		ainta	Swap (BOI16_swap)	C++17	100 / 100	497 ms	90160 KiB

swap

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 262144
using namespace std;
int w[262144], n, res[262144], R[262144];
vector<int>P[262144], D[262144], U[262144];
int Get(int nd, int x) {
	int t = lower_bound(P[nd].begin(), P[nd].end(), x + 1) - P[nd].begin();
	if (t == 0)return nd;
	return D[nd][t - 1];
}
int Get2(int nd, int x) {
	if (x == 0)return nd;
	return D[nd][x - 1];
}
int A[262144], B[262144];
void Do(int a) {
	if (a * 2 >= 262144) {
		R[a] = a;
		return;
	}
	int c1 = a * 2, c2 = a * 2 + 1;
	Do(c1);
	Do(c2);
	int CA = 0, CB = 0;
	for (auto &t : P[c1]) if (t < w[c1])A[CA++] = t;
	A[CA++] = w[c1];
	for (auto &t : P[c1]) if (t > w[c1])A[CA++] = t;
	for (auto &t : P[c2]) if (t < w[c2])B[CB++] = t;
	B[CB++] = w[c2];
	for (auto &t : P[c2]) if (t > w[c2])B[CB++] = t;

	int pA = 0, pB = 0, ppA = 0, ppB = 0;
	int ta1 = Get(c1, w[c1]);
	int tb2 = Get(c2, w[c1]);
	while (pA < CA || pB < CB) {
		if (pB == CB || (pA < CA && A[pA] < B[pB])) {
			if (A[pA] != w[c1])ppA++;
			P[a].push_back(A[pA++]);
		}
		else {
			if (B[pB] != w[c2])ppB++;
			P[a].push_back(B[pB++]);
		}
		int x = P[a].back();
		if (x < w[c1] && x < w[c2]) {
			D[a].push_back(a);
			U[a].push_back(0);
		}
		else if (w[c1] <= x && w[c1] < w[c2]) {
			int num = Get2(c1, ppA);
			D[a].push_back(num);
			U[a].push_back(1);
		}
		else {
			int a1 = ta1;
			int a2 = Get2(c2, ppB);
			int b1 = Get2(c1, ppA);
			int b2 =  tb2;
			int ck = 0;
			if (min(a1, a2) != min(b1, b2)) {
				if (min(a1, a2) < min(b1, b2))ck = 1;
				else ck = 2;
			}
			else{
				if ((w[c1] <= x) == (a1 < b2)) ck = 1;
				else ck = 2;
			}
			if (ck == 1) D[a].push_back(a2);
			else D[a].push_back(b1);
			U[a].push_back(ck + 1);
		}
	}
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	for (i = n + 1; i <= 262143; i++)w[i] = i;
	Do(1);
	for (i = 1; i <= n; i++) {
		int t = lower_bound(P[i].begin(), P[i].end(), w[i]) - P[i].begin();
		if (t == 0) continue;
		t--;
		if (U[i][t] == 1) {
			swap(w[i], w[i * 2]);
		}
		if (U[i][t] == 2) {
			swap(w[i], w[i * 2 + 1]);
		}
		if (U[i][t] == 3) {
			swap(w[i], w[i * 2]);
			swap(w[i], w[i * 2 + 1]);
		}
	}
	for (i = 1; i <= n; i++)printf("%d ", w[i]);
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:79:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &w[i]);
                          ~~~~~^~~~~~~~~~~~~

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