Submission #44703

#	Time	Username	Problem	Language	Result	Execution time	Memory
44703		cheater2k	Swap (BOI16_swap)	C++14	68 / 100	1092 ms	217852 KiB

swap

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int MAX = 1500005;
const int INF = 1e9;

typedef pair<int, int> ii;

int n, a[N], id;
vector <ii> vec[MAX];
int best[MAX];
map <int, int> mp[N];

void merge(vector <ii> &C, const vector <ii> &A, const vector <ii> &B) {
	for (int ia = 0, ib = 0; ia < A.size() || ib < B.size(); ) {
		if (ib == B.size() || (ia < A.size() && A[ia].first < B[ib].first)) {
			C.push_back(A[ia++]);
		} else {
			C.push_back(B[ib++]);
		}
	}
}

int dp(int v, int val) {
	if (val == INF) return 0; // empty vector
	if (mp[v].find(val) != mp[v].end()) {
		return mp[v][val];
	}

	mp[v][val] = ++id;
	int curid = id;
	int l = (v * 2 <= n) ? a[v * 2] : INF;
	int r = (v * 2 + 1 <= n) ? a[v * 2 + 1] : INF;

	int w[3] = {val, l, r};
	if (w[0] < min(w[1], w[2])) {
		vec[curid].push_back(make_pair(v, w[0]));
		merge(vec[curid], vec[dp(v << 1, w[1])], vec[dp(v << 1 | 1, w[2])]);
	}
	else if (w[1] < min(w[0], w[2])) {
		vec[curid].push_back(make_pair(v, w[1]));
		merge(vec[curid], vec[dp(v << 1, w[0])], vec[dp(v << 1 | 1, w[2])]);
	}
	else {
		// -> w[2], w[0], w[1]
		// -> w[2], w[1], w[0]
		vector <ii> cand[2];
		cand[0].push_back(make_pair(v, w[2]));
		cand[1].push_back(make_pair(v, w[2]));
		merge(cand[0], vec[dp(v << 1, w[0])], vec[dp(v << 1 | 1, w[1])]);
		merge(cand[1], vec[dp(v << 1, w[1])], vec[dp(v << 1 | 1, w[0])]);

		if (cand[0] < cand[1]) {
			best[curid] = 0;
			vec[curid] = cand[0];
		} else {
			best[curid] = 1;
			vec[curid] = cand[1];
		}
	}

	// printf("dp %d %d\n", v, val);
	// for (auto &i : vec[curid]) {
	// 	printf("%d ", i.second);
	// }
	// printf("\n");
	return curid;
}

void trace(int v, int val) {
	if (val == INF) return;
	int l = (v * 2 <= n) ? a[v * 2] : INF;
	int r = (v * 2 + 1 <= n) ? a[v * 2 + 1] : INF;

	int w[3] = {val, l, r};
	if (w[0] < min(w[1], w[2])) {
		a[v] = w[0];
		trace(v << 1, w[1]);
		trace(v << 1 | 1, w[2]);
	}
	else if (w[1] < min(w[0], w[2])) {
		a[v] = w[1];
		trace(v << 1, w[0]);
		trace(v << 1 | 1, w[2]);
	}
	else {
		a[v] = w[2];
		int curid = dp(v, val);
		trace(v << 1, w[best[curid]]);
		trace(v << 1 | 1, w[best[curid] ^ 1]);
	}
}

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

	dp(1, a[1]);
	trace(1, a[1]);

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

Compilation message (stderr)

swap.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
swap.cpp:16:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int ia = 0, ib = 0; ia < A.size() || ib < B.size(); ) {
                           ~~~^~~~~~~~~~
swap.cpp:16:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int ia = 0, ib = 0; ia < A.size() || ib < B.size(); ) {
                                            ~~~^~~~~~~~~~
swap.cpp:17:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ib == B.size() || (ia < A.size() && A[ia].first < B[ib].first)) {
       ~~~^~~~~~~~~~~
swap.cpp:17:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ib == B.size() || (ia < A.size() && A[ia].first < B[ib].first)) {
                          ~~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:98: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: 0 / 32