| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 402595 |
2021-05-12T02:53:36 Z |
wnsduds1 |
대표 선수 (KOI11_player) |
C |
|
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);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
