oj.uz

답안 #343898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343898 2021-01-04T17:38:19 Z flappybird 중앙값 배열 (balkan11_medians) C++14
5 / 100
 300 ms 9084 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAX 602020
int l[MAX], r[MAX];
int tree[MAX];
int arr[MAX];
int s;
vector<int>ans;
void init(int x = 1) {
	if (x >= s) {
		l[x] = r[x] = x - s + 1;
		return;
	}
	init(x * 2);
	init(x * 2 + 1);
	l[x] = l[x * 2];
	r[x] = r[x * 2 + 1];
}
void update(int loc) {
	if (loc == 0) return;
	tree[loc]++;
	update(loc / 2);
}
int sumquery(int low, int high, int loc = 1) {
	if (l[loc] == low && r[loc] == high) return tree[loc];
	else if (r[loc * 2] >= high) return sumquery(low, high, loc * 2);
	else if (l[loc * 2 + 1] <= low) return sumquery(low, high, loc * 2 + 1);
	else return sumquery(low, r[loc * 2], loc * 2) + sumquery(l[loc * 2 + 1], high, loc * 2 + 1);
}
int main(void) {
	int N;
	cin >> N;
	s = 1 << (int)ceil(log2(2 * N - 1));
	int i;
	init();
	int a;
	cin >> a;
	ans.push_back(a);
	update(a);
	arr[a] = 1;
	int p, q;
	p = 1;
	q = 2 * N - 1;
	for (i = 1; i <= N - 1; i++) {
		cin >> a;
		if (arr[a] == 0) {
			ans.push_back(a);
			update(a);
			arr[a] = 1;
			if (sumquery(1, a) < sumquery(a, 2 * N - 1)) {
				while (arr[p] == 1) p++;
				ans.push_back(p);
				update(p);
				arr[p] = 1;
			}
			else {
				while (arr[q] == 1) q--;
				ans.push_back(q);
				update(q);
				arr[q] = 1;
			}
		}
		else {
			if (sumquery(1, a) < sumquery(a, 2 * N - 1)) {
				while (arr[p] == 1) p++;
				ans.push_back(p);
				update(p);
				arr[p] = 1;
				while (arr[p] == 1) p++;
				ans.push_back(p);
				update(p);
				arr[p] = 1;
			}
			else if (sumquery(1, a) > sumquery(a, 2 * N - 1)) {
				while (arr[q] == 1) q--;
				ans.push_back(q);
				update(q);
				arr[q] = 1;
				while (arr[q] == 1) q--;
				ans.push_back(q);
				update(q);
				arr[q] = 1;
			}
			else {
				while (arr[p] == 1) p++;
				ans.push_back(p);
				update(p);
				arr[p] = 1;
				while (arr[q] == 1) q--;
				ans.push_back(q);
				update(q);
				arr[q] = 1;
			}
		}
	}
	for (auto i : ans) cout << i << endl;
}

Subtask #1
5.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 1 ms 376 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Incorrect 2 ms 364 KB Output isn't correct
12 Incorrect 4 ms 364 KB Output isn't correct
13 Incorrect 5 ms 364 KB Output isn't correct

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 492 KB Output isn't correct
2 Incorrect 21 ms 748 KB Output isn't correct
3 Incorrect 40 ms 1004 KB Output isn't correct
4 Incorrect 93 ms 1600 KB Output isn't correct
5 Incorrect 162 ms 2792 KB Output isn't correct
6 Execution timed out 330 ms 5348 KB Time limit exceeded
7 Execution timed out 508 ms 9084 KB Time limit exceeded