Submission #28676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28676	2017-07-16T08:35:54 Z	탕탕탕! 핑거팁 니 맘을 겨눌게~(#1190, cls327, archane5276, ly0829)	Wine Tasting (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, 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

#	Verdict	Execution time	Memory	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	-