oj.uz

답안 #60484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60484 2018-07-24T08:56:58 Z junodeveloper 중앙값 배열 (balkan11_medians) C++17
100 / 100
 59 ms 5564 KB 
#include <bits/stdc++.h>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
using namespace std;
const int BIT_SIZE = 1<<20;
int _bit[BIT_SIZE+1];
void bit_update(int p, int x) { for(int i=p; i<=BIT_SIZE; i+=i&-i) _bit[i] += x; }
int bit_query(int p) { int ret = 0; for(int i=p; i>0; i-=i&-i) ret += _bit[i]; return ret; }
int n, b[100010], a[200010], p1[100010], p2[100010], c1,c2;
bool chk[200010];
int getc1() {
	while(c1 <=2*n-1 && chk[c1]) c1++;
	return c1;
}
int getc2() {
	while(c2 && chk[c2]) c2--;
	return c2;
}
int main() {
	scanf("%d", &n);
	c1 = 1, c2 = 2*n-1;
	for(int i=1; i<=n; i++) {
		scanf("%d", b+i);
		if(i == 1) {
			chk[b[i]] = 1;
			continue;
		}
		if(b[i-1] > b[i]) {
			if(!chk[b[i]]) chk[p1[i] = b[i]] = 1, chk[p2[i] = getc1()] = 1;
			else chk[p1[i] = getc1()] = 1, chk[p2[i] = getc1()] = 1;
		} else if(b[i-1] < b[i]) {
			if(!chk[b[i]]) {
				chk[p1[i] = b[i]] = 1, chk[p2[i] = getc2()] = 1;
				//printf("(1) i:%d %d %d\n", i, p1[i], p2[i]);
			} else {
				chk[p1[i] = getc2()] = 1, chk[p2[i] = getc2()] = 1;
				//printf("(2) i:%d %d %d\n", i, p1[i], p2[i]);
			}
		} else {
			chk[p1[i] = getc1()] = 1, chk[p2[i] = getc2()] = 1;
			//printf("(3) i:%d %d %d\n", i, p1[i], p2[i]);
		}
	}
	//printf("c1 : %d, c2 : %d\n", c1, c2);
	a[1] = b[1];
	for(int i=2; i<=n; i++) {
		a[2*(i-1)] = p1[i];
		a[2*(i-1)+1] = p2[i];
	}
	for(int i=1; i<2*n; i++) printf("%d ", a[i]);
	return 0;
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
medians.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 644 KB Output is correct
2 Correct 5 ms 800 KB Output is correct
3 Correct 7 ms 972 KB Output is correct
4 Correct 16 ms 1436 KB Output is correct
5 Correct 27 ms 2056 KB Output is correct
6 Correct 47 ms 3520 KB Output is correct
7 Correct 59 ms 5564 KB Output is correct