oj.uz

답안 #28676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
28676 2017-07-16T08:35:54 Z 탕탕탕! 핑거팁 니 맘을 겨눌게~(#1190, cls327, archane5276, ly0829) 포도주 시음 (FXCUP2_wine) C
0 / 1
 0 ms 1116 KB 
#include <stdio.h>

#define LEFT_CHILD(x)    (2*x + 1)
#define RIGHT_CHILD(x) (2*x + 2)
#define PARENT(x)        ((x-1)/2)
#define SWAP(a,b)  {int t; t = a; a=b; b=t;}

void HeapSort(int *base, int n);
void InitHeap(int *base, int n);
void MakeHeap(int *base, int n);

void HeapSort(int *base, int n)
{
	int on = n;
	InitHeap(base, n);
	n--;
	SWAP(base[0], base[n]);
	while (n>1)
	{

		MakeHeap(base, n);
		n--;
		SWAP(base[0], base[n]);
	}
}

void InitHeap(int *base, int n)
{
	int pa = 0;
	int now;
	int i;
	for (i = 1; i<n; i++)
	{
		now = i;
		while (now>0)
		{
			pa = PARENT(now);
			if (base[now]>base[pa])
			{
				SWAP(base[now], base[pa]);
				now = pa;
			}
			else
			{
				break;
			}
		}
	}
}

int FindMaxIndex(int *base, int n, int now);
void MakeHeap(int *base, int n)
{
	int now = 0;
	int mp = 0;
	while (LEFT_CHILD(now) < n)
	{
		int mp = FindMaxIndex(base, n, now);
		if (mp == now)
		{
			break;
		}
		SWAP(base[mp], base[now]);
		now = mp;
	}
}

int FindMaxIndex(int *base, int n, int now)
{
	int lc = LEFT_CHILD(now);
	int rc = RIGHT_CHILD(now);

	if (rc >= n)
	{
		if (base[now]<base[lc])
		{
			return lc;
		}
		return now;
	}
	if (base[lc]<base[rc])
	{
		return rc;
	}
	return lc;
}

int main()
{
	int N, K, i, j = 1, k = 1;
	long long result = 0;
	int temp = 0, prev = 0;
	int *arr;
	scanf("%d %d", &N, &K);
	arr = (int*)malloc(sizeof(int)*N);
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	HeapSort(arr, N);
	for (i = 1; i <= K; i++) {
		if (i % 2 == 1) {
			if (i == 1) {
				temp = arr[N - i];
				result += temp;
			}
			else {
				temp = arr[N - i + k];
				result += temp - prev;
				k++;
			}
		}
		else {
			prev = arr[i - (j + 1)];
			j++;
		}
	}
	printf("%lld", result);
}

Compilation message

wine.c: In function 'HeapSort':
wine.c:14:6: warning: unused variable 'on' [-Wunused-variable]
  int on = n;
      ^
wine.c: In function 'MakeHeap':
wine.c:55:6: warning: unused variable 'mp' [-Wunused-variable]
  int mp = 0;
      ^
wine.c: In function 'main':
wine.c:95:14: warning: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
  arr = (int*)malloc(sizeof(int)*N);
              ^
wine.c:95:14: warning: incompatible implicit declaration of built-in function 'malloc'
wine.c:95:14: note: include '<stdlib.h>' or provide a declaration of 'malloc'
wine.c:94:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ^
wine.c:97:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ^

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1116 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 0 ms 1116 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 0 ms 1116 KB Output is correct
9 Correct 0 ms 1116 KB Output is correct
10 Incorrect 0 ms 1116 KB Output isn't correct
11 Halted 0 ms 0 KB -