Submission #402593

#	Time	Username	Problem	Language	Result	Execution time	Memory
402593		wnsduds1	대표 선수 (KOI11_player)	C11	0 / 20	1092 ms	8188 KiB

player

#include<stdio.h>
#include<stdlib.h>
typedef struct list {
	int v;
	int value;
}list;
void insert(list *x, list value);
list del(list *x);
list init(list arr[][101],list que[], int n);
void q_sort(list *arr, int index_s, int index_e);
int bottom = 0;
int front[1001] = { 0, };
int abs_min = 987654321;
int main() {

	int n, m, i, j, k;
	list arr[1001][1001];
	list que[10001];
	list max, tmp, value;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++)
	{
		for (k = 0; k < m; k++)
		{
			scanf("%d", &value.value);
			value.v = i;
			arr[i][k] = value;
			q_sort(arr[i], 0, k - 1);
		}
	}
	if (n == 1)
	{
		printf("%d", 0);
		return 0;
	}

	max=init(arr,que, n);
	abs_min = (max.value - que[1].value) > abs_min ? abs_min : (max.value - que[1].value);


	while (1)
	{
		
		tmp = del(que);

		if (front[tmp.v] < m)
		{
			if (arr[tmp.v][front[tmp.v]].value > max.value)
			{
				insert(que, max);
				max = arr[tmp.v][front[tmp.v]];
				abs_min = (max.value - que[1].value) > abs_min ? abs_min : (max.value - que[1].value);
			}
			else {
				insert(que, arr[tmp.v][front[tmp.v]]);
				abs_min = (max.value - que[1].value) > abs_min ? abs_min : (max.value - que[1].value);
			}
			front[tmp.v] += 1;
		}
		else {
			break;
		}
		
		
	}
	printf("%d", abs_min);
	
	
	return 0;
}
list init(list arr[][101], list que[], int n)
{
	list return_value = { 1002,987654321 };
	int index;
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			return_value = arr[i][front[i]];
			index = arr[i][front[i]].v;
		}
		else {
			if (return_value.value < arr[i][front[i]].value)
			{
				return_value = arr[i][front[i]];
				index = arr[i][front[i]].v;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (i != index)
		{
			insert(que, arr[i][front[i]]);
		}
		front[i] += 1;
	}

	return return_value;

}
void insert(list *x, list value)
{
	if (bottom == 0)
	{
		bottom++;
		x[bottom] = value;
	}
	else {
		int index;
		list tmp;
		bottom++;
		x[bottom] = value;
		index = bottom;
		while (index != 1 && x[index].value < x[index / 2].value)
		{
			tmp = x[index];
			x[index] = x[index / 2];
			x[index / 2] = tmp;
			index /= 2;
		}
	}

}
list del(list *x)
{
	list return_value;
	int index = 1;
	list tmp;
	return_value = x[index];
	x[index] = x[bottom];
	bottom -= 1;
	while (index * 2 <= bottom && (x[index].value > x[index*2].value || x[index].value > x[index * 2 + 1].value))
	{
		if (x[index * 2].value < x[index * 2 + 1].value)
		{
			tmp = x[index];
			x[index] = x[index * 2];
			x[index * 2] = tmp;
			index = index * 2;
		}
		else {
			tmp = x[index];
			x[index] = x[index * 2+1];
			x[index * 2+1] = tmp;
			index = index * 2+1;
		}
	}
	return return_value;
}
void q_sort(list *x, int index_s, int index_e)
{
	if (index_s >= index_e)
	{
		return;
	}
	else {
		int pit = (index_s + index_e) / 2;
		int l = index_s, r = index_e;
		list tmp;
		while (l < r)
		{
			while (l < r&&x[l].value < x[pit].value)
				l++;
			while (l < r&&x[r].value >= x[pit].value)
				r--;
			if (l == pit)
				pit = r;

			tmp = x[r];
			x[r] = x[l];
			x[l] = tmp;

		}
		tmp = x[r];
		x[r] = x[pit];
		x[pit] = tmp;
		pit = r;
		q_sort(x, index_s, pit - 1);
		q_sort(x, pit +1, index_e);
	}
}

Compilation message (stderr)

player.c: In function 'main':
player.c:37:11: warning: passing argument 1 of 'init' from incompatible pointer type [-Wincompatible-pointer-types]
   37 |  max=init(arr,que, n);
      |           ^~~
      |           |
      |           list (*)[1001]
player.c:9:16: note: expected 'list (*)[101]' but argument is of type 'list (*)[1001]'
    9 | list init(list arr[][101],list que[], int n);
      |           ~~~~~^~~~~~~~~~
player.c:16:15: warning: unused variable 'j' [-Wunused-variable]
   16 |  int n, m, i, j, k;
      |               ^
player.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d %d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~
player.c:25:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |    scanf("%d", &value.value);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10