Submission #258362

#	Time	Username	Problem	Language	Result	Execution time	Memory
258362		maximath_1	Swap (BOI16_swap)	C++11	100 / 100	59 ms	5300 KiB

swap

#include <iostream>
using namespace std;

int n, arr[200005], used[400005];
const int inf = 1e9 + 69;

int query(int id){
	int rs = inf;
	for(; id; id >>= 1){
		if(used[id] != 1) rs = min(rs, arr[id]);
		if(!used[id]) break;

		if(id % 2 == 1 && used[id - 1]){
			rs = min(rs, arr[id - 1]);
			if(used[id - 1] == 1) break;
		}
	}
	return rs;
}

void erase(int id, int val){
	for(; id; id >>= 1){
		if(arr[id] == val){
			used[id] = 0;
			break;
		}

		if(id % 2 == 1){
			if(arr[id - 1] == val){
				used[id - 1] = used[id] = 1;
				break;
			}else used[id - 1] = 0;
		}

		used[id] = 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> arr[i];
		used[i] = 2;
	}
	used[1] = 0;

	for(int i = 1; i <= n; i ++){
		int rs = query(i);
		int upl = (i * 2 <= n ? arr[i * 2] : inf);
		int upr = (i * 2 + 1 <= n ? arr[i * 2 + 1] : inf);
		int v = min(rs, min(upl, upr));

		cout << v;
		if(i == n) cout << endl;
		else cout << " ";

		if(rs == v){
			used[i * 2] = used[i * 2 + 1] = 0;
			erase(i, rs);
		}else if(upl == v){
			used[i * 2] = 1;
			used[i * 2 + 1] = 0;
		}else if(upr == v){
			used[i * 2 + 1] = 1;
		}
	}

	return 0;
}

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