Submission #258776

#	Time	Username	Problem	Language	Result	Execution time	Memory
258776		vioalbert	Swap (BOI16_swap)	C++14	100 / 100	59 ms	7288 KiB

swap

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

const int N = 5e5+5, INF = 1e9;
int n;
int a[N], ans[N], state[N];

int get(int idx) {
	int ret = INF;
	while(idx > 0) {
		if(state[idx] != 1) ret = min(ret, a[idx]);
		if(state[idx] == 0) break;
		if((idx&1) && state[idx^1] != 0) {
			ret = min(ret, a[idx^1]);
			if(state[idx^1] == 1) break;
		}
		idx >>= 1;
	}
	return ret;
}

void change(int idx, int val) {
	while(idx > 0) {
		if(a[idx] == val) {
			state[idx] = 0;
			return;
		}
		if(idx&1) {
			if(a[idx^1] == val) {
				state[idx^1] = state[idx] = 1;
				return;
			} else {
				state[idx^1] = 0;
			}
		}
		state[idx] = 1;
		idx >>= 1;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	fill_n(a, N, INF);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		state[i] = (i==1)?0:-1;
	}

	for(int i = 1; i <= n; i++) {
		int x = get(i);
		ans[i] = min({x, a[i<<1], a[i<<1|1]});

		if(ans[i] == x) {
			state[i<<1] = state[i<<1|1] = 0;
			change(i, x);
		} else if(ans[i] == a[i<<1]) {
			state[i<<1] = 1, state[i<<1|1] = 0;
		} else {
			state[i<<1|1] = 1;
		}
	}

	for(int i = 1; i <= n; i++)
		cout << ans[i] << " \n"[i==n];

	return 0;
}

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