oj.uz

Submission #56175

# Submission time Handle Problem Language Result Execution time Memory
56175 2018-07-10T07:36:54 Z 윤교준(#1582) Swap (BOI16_swap) C++11
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 200005;

struct NOD {
	NOD(NOD *l, NOD *r, int dt, bool *c)
		: l(l), r(r), dt(dt), c(c) {}
	NOD *l, *r;
	int dt;
	bool *c;

	int get() {
		if(dt) return dt;
		if(*c) return l -> get();
		return min(l -> get(), r -> get());
	}
	bool upd(int x) {
		if(dt) {
			if(dt != x) return false;
			dt = INF;
			return true;
		}
		if(*c) return l -> upd(x);
		if(l -> upd(x)) {
			return true;
		}
		if(r -> upd(x)) {
			*c = true;
			swap(*l, *r);
			return true;
		}
		return false;
	}
};

NOD *nod[MAXN];

int A[MAXN];
int N;

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	for(int i = 1; i <= N; i++)
		nod[i] = new NOD(NULL, NULL, A[i], NULL);
	for(int i = 2; i <= N; i++) {
		NOD *a = nod[i/2], *b = nod[i];
		bool *c = new bool(false);
		nod[i/2] = new NOD(a, b, 0, c);
		nod[i] = new NOD(b, a, 0, c);
	}
	for(int i = 1, x; i <= N; i++) {
		x = nod[i] -> get();
		nod[i] -> upd(x);
		printf("%d ", x);
	}
	puts("");
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 32.0

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