Submission #21000

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21000	2017-03-27T10:57:50 Z	model_code	Swap (BOI16_swap)	C++11	100 / 100	183 ms	38064 KB

swap

#include <iostream>
#include <climits>

using namespace std;

struct T {
	T(int val) : val(val) { }
	T(T* a, T* b, bool* d) : val(0), a(a), b(b), d(d) { }
	
	int val;
	T* a;
	T* b;
	bool* d;
	
	int query() {
		if(val) {
			return val;
		} else if(*d) {
			return a->query();
		} else {
			return min(a->query(), b->query());
		}
	}
	bool del(int x) {
		if(val) {
			if(val == x) {
				val = INT_MAX;
				return true;
			}
			return false;
		} else if(*d) {
			return a->del(x);
		} else {
			if(a->del(x)) {
				*d = true;
				return true;
			}
			if(b->del(x)) {
				*d = true;
				swap(*a, *b);
				return true;
			}
			return false;
		}
	}
};

T* t[202020];

int main() {
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		t[i] = new T(x);
	}
	
	for(int i = 2; i <= n; ++i) {
		T* a = t[i / 2];
		T* b = t[i];
		bool* d = new bool(false);
		t[i / 2] = new T(a, b, d);
		t[i] = new T(b, a, d);
	}
	
	for(int i = 1; i <= n; ++i) {
		int val = t[i]->query();
		t[i]->del(val);
		if(i != 1) cout << ' ';
		cout << val;
	}
	cout << '\n';
	
	return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

11.0 / 11.0

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

Subtask #3

27.0 / 27.0

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

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3612 KB	Output is correct
2	Correct	0 ms	3612 KB	Output is correct
3	Correct	0 ms	3612 KB	Output is correct
4	Correct	0 ms	3612 KB	Output is correct
5	Correct	0 ms	3612 KB	Output is correct
6	Correct	0 ms	3612 KB	Output is correct
7	Correct	0 ms	3612 KB	Output is correct
8	Correct	0 ms	3612 KB	Output is correct
9	Correct	0 ms	3612 KB	Output is correct
10	Correct	0 ms	3612 KB	Output is correct
11	Correct	0 ms	3744 KB	Output is correct
12	Correct	0 ms	3744 KB	Output is correct
13	Correct	0 ms	3744 KB	Output is correct
14	Correct	0 ms	3744 KB	Output is correct
15	Correct	0 ms	3744 KB	Output is correct
16	Correct	26 ms	12192 KB	Output is correct
17	Correct	43 ms	12192 KB	Output is correct
18	Correct	26 ms	12192 KB	Output is correct
19	Correct	46 ms	12192 KB	Output is correct
20	Correct	33 ms	12192 KB	Output is correct

Subtask #5

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3612 KB	Output is correct
2	Correct	0 ms	3612 KB	Output is correct
3	Correct	0 ms	3612 KB	Output is correct
4	Correct	0 ms	3612 KB	Output is correct
5	Correct	0 ms	3612 KB	Output is correct
6	Correct	0 ms	3612 KB	Output is correct
7	Correct	0 ms	3612 KB	Output is correct
8	Correct	0 ms	3612 KB	Output is correct
9	Correct	0 ms	3612 KB	Output is correct
10	Correct	0 ms	3612 KB	Output is correct
11	Correct	0 ms	3744 KB	Output is correct
12	Correct	0 ms	3744 KB	Output is correct
13	Correct	0 ms	3744 KB	Output is correct
14	Correct	0 ms	3744 KB	Output is correct
15	Correct	0 ms	3744 KB	Output is correct
16	Correct	26 ms	12192 KB	Output is correct
17	Correct	43 ms	12192 KB	Output is correct
18	Correct	26 ms	12192 KB	Output is correct
19	Correct	46 ms	12192 KB	Output is correct
20	Correct	33 ms	12192 KB	Output is correct
21	Correct	149 ms	38064 KB	Output is correct
22	Correct	136 ms	38064 KB	Output is correct
23	Correct	146 ms	38064 KB	Output is correct
24	Correct	169 ms	38064 KB	Output is correct
25	Correct	183 ms	38064 KB	Output is correct