Submission #259014

#	Time	Username	Problem	Language	Result	Execution time	Memory
259014		Berted	Swap (BOI16_swap)	C++14	100 / 100	355 ms	99704 KiB

swap

#include <iostream>
#include <algorithm>
#include <utility>
#include <assert.h>
#include <map>
#include <unordered_map>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#define vi vector<int>
#define pii pair<int, int>
#define ppi pair<int, pii>
#define fst first
#define snd second
using namespace std;
using namespace __gnu_pbds;

int n, ar[400001], res[400001];
ppi dp[200001][40];

int L[200001], R[200001], q[200001], qsz = 0;

inline bool comp()
{
	int ret = 0;
	for (int i = 0; i < qsz; i++)
	{
		int u = q[i];
		if (dp[u][L[u]].fst < dp[u][R[u]].fst) {break;}
		if (dp[u][L[u]].fst > dp[u][R[u]].fst) {ret = 1; break;}
		if ((u << 1) <= n) 
		{
			q[qsz++] = u << 1;
			L[u << 1] = dp[u][L[u]].snd.fst;
			R[u << 1] = dp[u][R[u]].snd.fst;
		}
		if ((u << 1 | 1) <= n) 
		{
			q[qsz++] = u << 1 | 1;
			L[u << 1 | 1] = dp[u][L[u]].snd.snd;
			R[u << 1 | 1] = dp[u][R[u]].snd.snd;
		}
	}
	qsz = 0;
	return ret;
}

inline void backtrack()
{
	for (int i = 0; i < qsz; i++)
	{
		int u = q[i];
		res[u] = dp[u][L[u]].fst;
		if ((u << 1) <= n) 
		{
			q[qsz++] = u << 1;
			L[u << 1] = dp[u][L[u]].snd.fst;
		}
		if ((u << 1 | 1) <= n) 
		{
			q[qsz++] = u << 1 | 1;
			L[u << 1 | 1] = dp[u][L[u]].snd.snd;
		}
	}
}

void solve(int x, int k)
{
	if (x <= n)
	{
		if (dp[x][k].fst == 0)
		{
			//cout << "Called DP " << x << " " << k << "\n";
			//cout << "Index : " << (x >> (k >> 1)) - (k & 1) << "\n";
			int mn = (ar[(x >> (k >> 1)) - (k & 1)]);
			if ((x << 1) <= n)     mn = min(mn, ar[x << 1]);
			if ((x << 1 | 1) <= n) mn = min(mn, ar[x << 1 | 1]);
			dp[x][k].fst = mn;
			if (ar[(x >> (k >> 1)) - (k & 1)] == mn)
			{
				dp[x][k].snd = {0, 0};
				solve(x << 1, 0); 
				solve(x << 1 | 1, 0);
			}
			else if (ar[x << 1] == mn)
			{
				dp[x][k].snd = {k + 2, 0};
				solve(x << 1, k + 2); 
				solve(x << 1 | 1, 0);
			}
			else
			{
				solve(x << 1, k + 2); solve(x << 1 | 1, 1);
				solve(x << 1, 0); solve(x << 1 | 1, k + 2);

				q[qsz++] = x << 1; L[x << 1] = k + 2; R[x << 1] = 0;
				q[qsz++] = x << 1 | 1; L[x << 1 | 1] = 1; R[x << 1 | 1] = k + 2;

				if (comp()) {dp[x][k].snd = {0, k + 2};}
				else {dp[x][k].snd = {k + 2, 1};}
			}
			
			//cout << "DP " << x << " " << k << "\n";
			//cout << dp[x][k].fst << " " << dp[x][k].snd.fst << " " << dp[x][k].snd.snd << "\n";
		}
	}
}

int main()
{
	//freopen("C.in", "r", stdin);
	//freopen("C.out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {cin >> ar[i];}
	solve(1, 0);
	q[qsz++] = 1; L[1] = 0;
	backtrack();
	for (int i = 1; i <= n; i++)
	{
		cout << res[i];
		if (i < n) cout << " ";
	}
	cout << "\n";
	return 0;
}

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