Submission #56897

#	Time	Username	Problem	Language	Result	Execution time	Memory
56897		ainta	Swap (BOI16_swap)	C++17	48 / 100	1083 ms	82264 KiB

swap

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 262144
using namespace std;
int w[262144], n, res[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];
}
void Do(int a) {
	if (a * 2 >= 262144) return;
	int c1 = a * 2, c2 = a * 2 + 1;
	Do(c1);
	Do(c2);
	for (auto &t : P[c1])P[a].push_back(t);
	for (auto &t : P[c2])P[a].push_back(t);
	P[a].push_back(w[c1]);
	P[a].push_back(w[c2]);
	sort(P[a].begin(), P[a].end());
	if (a == 1) {
		int t = -1;
	}
	for (auto &x : P[a]) {
		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 = Get(c1, x);
			D[a].push_back(num);
			U[a].push_back(1);
		}
		else {
			int a1 = Get(c1, w[c1]);
			int a2 = Get(c2, x);
			int b1 = Get(c1, x);
			int b2 = Get(c2, w[c1]);
			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 'void Do(int)':
swap.cpp:24:7: warning: unused variable 't' [-Wunused-variable]
   int t = -1;
       ^
swap.cpp: In function 'int main()':
swap.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:59: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: 0 / 20
• Subtask 5: 0 / 32