Submission #259010

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

swap

#include <iostream>
using namespace std;

int n, arr[200005], used[400005];
//0: operationnya pasti ga kepake, but the number still ther
//1: number is not there, operationnya dah kepake
//2: nothing, untouched
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 & 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 & 1){
			if(arr[id ^ 1] == val){
				used[id ^ 1] = used[id] = 1;
				break;
			}else used[id ^ 1] = 0;
		}

		used[id] = 1;
	}
}

#define parl (i << 1)
#define parr (parl | 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 = (parl <= n ? arr[parl] : inf);
		int upr = (parr <= n ? arr[parr] : inf);
		int v = min(rs, min(upl, upr));

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

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

	return 0;
}

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