Submission #259011

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259011	2020-08-07T03:02:31 Z	maximath_1	Swap (BOI16_swap)	C++11	100 / 100	72 ms	4008 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	15 ms	1256 KB	Output is correct
17	Correct	15 ms	1152 KB	Output is correct
18	Correct	24 ms	1152 KB	Output is correct
19	Correct	16 ms	1152 KB	Output is correct
20	Correct	19 ms	1152 KB	Output is correct

Subtask #5

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	15 ms	1256 KB	Output is correct
17	Correct	15 ms	1152 KB	Output is correct
18	Correct	24 ms	1152 KB	Output is correct
19	Correct	16 ms	1152 KB	Output is correct
20	Correct	19 ms	1152 KB	Output is correct
21	Correct	69 ms	3960 KB	Output is correct
22	Correct	65 ms	4008 KB	Output is correct
23	Correct	64 ms	3960 KB	Output is correct
24	Correct	70 ms	3932 KB	Output is correct
25	Correct	72 ms	3960 KB	Output is correct