Submission #19241


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>

#define A int
#define B int

typedef struct {
    A first;
    B second;
} pair;

int cmp_first(A a, A b)
{
    return a - b;
}

int cmp_second(B a, B b)
{
    return a - b;
}

int cmp_pair(pair a, pair b)
{
    int x = cmp_first(a.first, b.first);
    
    if (x != 0) return x;
    
    return cmp_second(a.second, b.second);
}

pair make_pair(A first, B second)
{
    pair p;
    
    p.first = first;
    p.second = second;
    
    return p;
}

#define Q pair

typedef struct _queue {
    Q value;
    int size;
    struct _queue *next;
    struct _queue *last;
} queue;

queue *push(queue *q, Q value)
{
    queue *tmp = malloc(sizeof(queue));
    
    tmp->value = value;
    tmp->next = NULL;
    tmp->last = tmp;
    
    if (q == NULL) {
        tmp->size = 1;
        
        return tmp;
    } else {
        q->size++;
        
        q->last->next = tmp;
        q->last = tmp;
        
        return q;
    }
}

queue *pop(queue *q)
{
    if (q->size == 1) {
        free(q);
        
        return NULL;
    } else {
        queue *tmp = q->next;
        
        tmp->size = q->size - 1;
        tmp->last = q->last;
        
        free(q);
        
        return tmp;
    }
}

Q front(queue *q)
{
    return q->value;
}

Q back(queue *q)
{
    return q->last->value;
}

int empty(queue *q)
{
    if (q == NULL) {
        return 1;
    } else {
        return 0;
    }
}

int size(queue *q)
{
    if (empty(q)) {
        return 0;
    } else {
        return q->size;
    }
}

void clear(queue *q)
{
    if (q->next != NULL) clear(q->next);
    
    free(q);
}

int n, m, x1, y1, x2, y2;
char s[500][501];
double a[250001];
int f[500][500];

int ok(double c)
{
    int i, j;
    queue *q = NULL;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            f[i][j] = 0;
        }
    }
    
    q = push(q, make_pair(x1 * 500 + y1, 0));
    
    while (!empty(q)) {
        pair p = front(q);
        int x, y, t;
        
        q = pop(q);
        
        x = p.first / 500;
        y = (p.first - x * 500) % m;
        t = p.second + 1;
        
        if (f[x][y] == 1) continue;
        
        f[x][y] = 1;
        
        if (x == x2 && y == y2) return 1;
        
        if (x > 0 && s[x - 1][y] != '#' && f[x - 1][y] == 0) {
            if ((s[x - 1][y] - '0') * a[t] >= c) {
                q = push(q, make_pair((x - 1) * 500 + y, t));
            }
        }
        
        if (x < n - 1 && s[x + 1][y] != '#' && f[x + 1][y] == 0) {
            if ((s[x + 1][y] - '0') * a[t] >= c) {
                q = push(q, make_pair((x + 1) * 500 + y, t));
            }
        }
        
        if (y > 0 && s[x][y - 1] != '#' && f[x][y - 1] == 0) {
            if ((s[x][y - 1] - '0') * a[t] >= c) {
                q = push(q, make_pair(x * 500 + y - 1, t));
            }
        }
        
        if (y < m - 1 && s[x][y + 1] != '#' && f[x][y + 1] == 0) {
            if ((s[x][y + 1] - '0') * a[t] >= c) {
                q = push(q, make_pair(x * 500 + y + 1, t));
            }
        }
    }
    
    return 0;
}

int main()
{
    int i, j;
    double l, r, mid;
    
    scanf("%d %d", &n, &m);
    
    for (i = 0; i < n; i++) scanf("%s", s[i]);
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (s[i][j] == 's') {
                x1 = i;
                y1 = j;
            } else if (s[i][j] == 'g') {
                x2 = i;
                y2 = j;
            }
        }
    }
    
    a[0] = 1;
    
    for (i = 1; i <= n * m; i++) a[i] = a[i - 1] * 0.99;
    
    l = 0;
    r = 10;
    mid = (l + r) / 2;
    
    for (i = 0; i < 100; i++) {
        if (ok(mid)) {
            l = mid;
            mid = (l + r) / 2;
        } else {
            r = mid;
            mid = (l + r) / 2;
        }
    }
    
    if (l < 1e-9) {
        puts("-1");
    } else {
        printf("%.12lf\n", l);
    }
    
    return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User kawatea
Language C (GCC 4.4.7)
Score 0
Code Size 4201 Byte
Status WA
Exec Time 2945 ms
Memory 4344 KB

Compile Error

./Main.c:125: warning: built-in function ‘y1’ declared as non-function
./Main.c: In function ‘main’:
./Main.c:192: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
./Main.c:194: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 60
WA × 4
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 20 ms 664 KB
00_mini_02.txt AC 21 ms 664 KB
00_mini_03.txt AC 19 ms 660 KB
00_mini_04.txt AC 18 ms 680 KB
00_mini_05.txt AC 20 ms 656 KB
00_sample_01.txt AC 20 ms 676 KB
00_sample_02.txt AC 20 ms 684 KB
01_rnd_01.txt AC 2324 ms 3328 KB
01_rnd_02.txt AC 305 ms 2556 KB
01_rnd_03.txt AC 44 ms 1156 KB
01_rnd_04.txt AC 183 ms 1524 KB
01_rnd_05.txt AC 39 ms 1008 KB
01_rnd_06.txt AC 24 ms 912 KB
01_rnd_07.txt AC 43 ms 1920 KB
01_rnd_08.txt AC 420 ms 3324 KB
01_rnd_09.txt AC 654 ms 3072 KB
01_rnd_10.txt AC 892 ms 2948 KB
01_rnd_11.txt AC 466 ms 2176 KB
01_rnd_12.txt AC 270 ms 1784 KB
01_rnd_13.txt AC 79 ms 920 KB
01_rnd_14.txt AC 1173 ms 2688 KB
01_rnd_15.txt AC 500 ms 2040 KB
01_rnd_16.txt AC 29 ms 1560 KB
01_rnd_17.txt AC 486 ms 2040 KB
01_rnd_18.txt AC 22 ms 1048 KB
01_rnd_19.txt AC 27 ms 1916 KB
01_rnd_20.txt AC 24 ms 1788 KB
02_maxrnd_01.txt AC 624 ms 3840 KB
02_maxrnd_02.txt AC 449 ms 4344 KB
02_maxrnd_03.txt AC 717 ms 4088 KB
02_maxrnd_04.txt AC 1284 ms 4340 KB
02_maxrnd_05.txt AC 708 ms 4096 KB
02_maxrnd_06.txt AC 2595 ms 4344 KB
02_maxrnd_07.txt AC 236 ms 3956 KB
02_maxrnd_08.txt AC 133 ms 3952 KB
02_maxrnd_09.txt AC 2461 ms 3972 KB
02_maxrnd_10.txt AC 370 ms 4092 KB
02_maxrnd_11.txt AC 2175 ms 3960 KB
02_maxrnd_12.txt AC 980 ms 4084 KB
02_maxrnd_13.txt AC 2274 ms 4220 KB
02_maxrnd_14.txt AC 1520 ms 3960 KB
02_maxrnd_15.txt AC 259 ms 3960 KB
02_maxrnd_16.txt AC 1154 ms 3968 KB
02_maxrnd_17.txt AC 934 ms 3952 KB
02_maxrnd_18.txt AC 101 ms 3832 KB
02_maxrnd_19.txt AC 82 ms 3832 KB
03_hard_01.txt AC 2656 ms 3828 KB
03_hard_02.txt AC 2779 ms 3828 KB
03_hard_03.txt WA 88 ms 3840 KB
03_hard_04.txt WA 103 ms 3836 KB
03_hard_05.txt AC 2701 ms 3840 KB
03_hard_06.txt AC 2783 ms 3832 KB
03_hard_07.txt WA 88 ms 3820 KB
03_hard_08.txt WA 102 ms 3832 KB
04_open_01.txt AC 2945 ms 3932 KB
04_open_02.txt AC 2814 ms 3832 KB
05_minihard_01.txt AC 23 ms 792 KB
05_minihard_02.txt AC 24 ms 788 KB
05_minihard_03.txt AC 23 ms 764 KB
05_minihard_04.txt AC 22 ms 788 KB
05_minihard_05.txt AC 25 ms 884 KB
05_minihard_06.txt AC 28 ms 784 KB
05_minihard_07.txt AC 22 ms 788 KB
05_minihard_08.txt AC 22 ms 784 KB