oj.uz

답안 #147294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147294 2019-08-28T18:35:37 Z cerberus Swap (BOI16_swap) C++17
100 / 100
 230 ms 23928 KB 
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 4e5 + 10, inf = 1e9 + 42;

struct node {
	int val;
	node *l, *r;
	node(node *_l, node *_r, int _val = inf) {
		l = _l;
		r = _r;
		val = _val;
	}
};

node* a[N];

int get_min(node* cur);
bool del(node *cur, int x);

int main() {
	int n; cin >> n;
	vector<int> p(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		a[i] = new node(NULL, NULL, x);
		p[i] = x;
	}
	for (int i = n + 1; i <= 2 * n + 1; ++i) {
		a[i] = new node(NULL, NULL);
	}
	vector<int> q(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int x = get_min(a[i]);
		x = min(x, get_min(a[2 * i]));
		x = min(x, get_min(a[2 * i + 1]));
		// cout << x << ' ';
		q[i] = x;
		if (get_min(a[2 * i]) == x) {
			swap(a[2 * i], a[i]);
		} else if (get_min(a[2 * i + 1]) == x) {
			node *temp = new node(a[i], a[2 * i]);
			a[i] = a[2 * i + 1];
			a[2 * i] = a[2 * i + 1] = temp;
		}
		del(a[i], x);
	}
	vector<int> ans = q;
	for (int i = n; i > 1; --i) {
		if (q[i] != p[i]) {
			swap(q[i], q[i / 2]);
		}
	}
	assert(p == q);
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << ' ';
	}
	cout << endl;
}

int get_min(node* cur) {
	if (cur == NULL) {
		return inf;
	} else {
		int ans = cur->val;
		ans = min(ans, get_min(cur->l));
		ans = min(ans, get_min(cur->r));
		return ans;
	}
}

bool del(node *cur, int x) {
	if (cur == NULL) {
		return false;
	} else if (cur->val == x) {
		cur->val = inf;
		return true;
	} else {
		if (del(cur->l, x)) {
			cur->l = NULL;
		} else if (del(cur->r, x)) {
			cur->r = NULL;
		} else {
			return false;
		}
		return true;
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 424 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 424 KB Output is correct
16 Correct 42 ms 5712 KB Output is correct
17 Correct 44 ms 5752 KB Output is correct
18 Correct 43 ms 5752 KB Output is correct
19 Correct 54 ms 6200 KB Output is correct
20 Correct 53 ms 6184 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 424 KB Output is correct
16 Correct 42 ms 5712 KB Output is correct
17 Correct 44 ms 5752 KB Output is correct
18 Correct 43 ms 5752 KB Output is correct
19 Correct 54 ms 6200 KB Output is correct
20 Correct 53 ms 6184 KB Output is correct
21 Correct 174 ms 22232 KB Output is correct
22 Correct 172 ms 22236 KB Output is correct
23 Correct 174 ms 22236 KB Output is correct
24 Correct 228 ms 23928 KB Output is correct
25 Correct 230 ms 23928 KB Output is correct