Submission #384202

#	Time	Username	Problem	Language	Result	Execution time	Memory
384202		pure_mem	Swap (BOI16_swap)	C++14	100 / 100	169 ms	17408 KiB

swap

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 5e5 + 12;
const int mod = 1e9 + 7;

int n, p[N];
map< pair<int, int>, int > dp;

int get(int v, int val){
	if(dp.count(MP(v, val)))
		return dp[MP(v, val)];
	if(val < min(p[v * 2], p[v * 2 + 1]))
		return v;
	if(p[v * 2] < p[v * 2 + 1])
		return dp[MP(v, val)] = get(v * 2, val);
	int mn = min(p[v * 2], val), mx = max(p[v * 2], mx);
	if(get(v * 2, mn) < get(v * 2 + 1, mn)){
		if(mn == val)
			return dp[MP(v, val)] = get(v * 2, val);
		else
			return dp[MP(v, val)] = get(v * 2 + 1, val); 	
	}
	else{
	    if(mn != val)
			return dp[MP(v, val)] = get(v * 2, val);
		else
			return dp[MP(v, val)] = get(v * 2 + 1, val);
	}
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(p, 0x3f, sizeof(p));
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> p[i];
    for(int i = 1;i <= n;i++){
    	if(p[i * 2 + 1] < min(p[i], p[i * 2])){
    		int mn = min(p[i], p[i * 2]), mx = max(p[i], p[i * 2]);
    		p[i] = p[i * 2 + 1], p[i * 2] = mx, p[i * 2 + 1] = mn;
    		if(get(i * 2, mn) < get(i * 2 + 1, mn))
    			p[i * 2] = mn, p[i * 2 + 1] = mx;
    	}
    	else if(p[i * 2] < p[i]){
    		swap(p[i], p[i * 2]);
    	}
    	cout << p[i] << " ";
    }
}                               

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