Submission #259011

#	Time	Username	Problem	Language	Result	Execution time	Memory
259011		maximath_1	Swap (BOI16_swap)	C++11	100 / 100	72 ms	4008 KiB

swap

#include <stdio.h>
#include <algorithm>
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(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d", 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));

		printf("%d%c", v, (i == n ? '\n' : ' '));

		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;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", arr + i);
   ~~~~~^~~~~~~~~~~~~~~

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