oj.uz

답안 #402595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402595 2021-05-12T02:53:36 Z wnsduds1 대표 선수 (KOI11_player) C
20 / 20
 296 ms 17044 KB 
#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[][1001],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[1001];
	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, m - 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[][1001], 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

player.c: In function 'main':
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
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 4 ms 8132 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8012 KB Output is correct
2 Correct 11 ms 8276 KB Output is correct
3 Correct 27 ms 8916 KB Output is correct
4 Correct 65 ms 10052 KB Output is correct
5 Correct 80 ms 10528 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 8012 KB Output is correct
2 Correct 100 ms 10792 KB Output is correct
3 Correct 109 ms 11544 KB Output is correct
4 Correct 128 ms 12084 KB Output is correct
5 Correct 158 ms 12612 KB Output is correct
6 Correct 167 ms 13352 KB Output is correct
7 Correct 213 ms 14788 KB Output is correct
8 Correct 244 ms 14880 KB Output is correct
9 Correct 256 ms 15912 KB Output is correct
10 Correct 296 ms 17044 KB Output is correct