답안 #28705

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

wine

#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, first = 0, end = 1;
	int *wine;
	long long int flavor = 0;
	scanf("%d %d", &N, &K);
	wine = (int*)malloc(sizeof(int)*N);
	for (i = 0; i < N; i++)
		scanf("%d", &wine[i]);
	HeapSort(wine, N);
	for (i = 0; i < K; i = i + 2) {
		if (i == 0) {
			flavor = wine[N - end];
			end++;
			continue;
		}
		flavor += wine[N - end] - wine[0 + first];
		end++;
		first++;
	}
	printf("%lld", flavor);
	return 0;
}

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:93:15: warning: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
  wine = (int*)malloc(sizeof(int)*N);
               ^
wine.c:93:15: warning: incompatible implicit declaration of built-in function 'malloc'
wine.c:93:15: note: include '<stdlib.h>' or provide a declaration of 'malloc'
wine.c:92:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ^
wine.c:95:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &wine[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	-