oj.uz

Submission #147285

# Submission time Handle Problem Language Result Execution time Memory
147285 2019-08-28T18:04:01 Z cerberus Swap (BOI16_swap) C++17
0 / 100
 2 ms 376 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);
void del(node *cur, int x);

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		a[i] = new node(NULL, NULL, x);
	}
	for (int i = n + 1; i <= 2 * n + 1; ++i) {
		a[i] = new node(NULL, NULL);
	}
	for (int i = 1; i <= n; ++i) {
		int x = get_min(a[i]);
		x = min(x, min(get_min(a[2 * i]), get_min(a[2 * i + 1])));
		cout << 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);
	}
}

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -