Submission #18998


Source Code Expand

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

#define A double
#define B int
#define C int

typedef struct {
    A first;
    B second;
    C third;
} tuple;

int cmp_first(A a, A b)
{
    if (a > b) {
        return 1;
    } else if (a == b) {
        return 0;
    } else {
        return -1;
    }
}

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

int cmp_third(C a, C b)
{
    return a - b;
}

int cmp_tuple(tuple a, tuple b)
{
    int x = cmp_first(a.first, b.first);
    
    if (x != 0) return x;
    
    x = cmp_second(a.second, b.second);
    
    if (x != 0) return x;
    
    return cmp_third(a.third, b.third);
}

tuple make_tuple(A first, B second, C third)
{
    tuple t;
    
    t.first = first;
    t.second = second;
    t.third = third;
    
    return t;
}

#define P tuple

typedef struct _priority_queue {
    P value;
    int size;
    struct _priority_queue *left;
    struct _priority_queue *right;
} priority_queue;

int cmp_queue(P a, P b)
{
    return cmp_tuple(a, b);
}

priority_queue *meld(priority_queue *a, priority_queue *b)
{
    priority_queue *tmp;
    
    if (a == NULL) return b;
    
    if (b == NULL) return a;
    
    if (cmp_queue(a->value, b->value) > 0) {
        tmp = a;
        a = b;
        b = tmp;
    }
    
    a->right = meld(a->right, b);
    
    tmp = a->left;
    a->left = a->right;
    a->right = tmp;
    
    return a;
}

priority_queue *push(priority_queue *a, P value)
{
    priority_queue *tmp = malloc(sizeof(priority_queue));
    int x;
    
    if (a == NULL) {
        x = 1;
    } else {
        x = a->size + 1;
    }
    
    tmp->value = value;
    tmp->left = NULL;
    tmp->right = NULL;
    
    tmp = meld(tmp, a);
    
    tmp->size = x;
    
    return tmp;
}

priority_queue *pop(priority_queue *a)
{
    priority_queue *tmp;
    int x = a->size - 1;
    
    tmp = meld(a->left, a->right);
    
    if (tmp != NULL) tmp->size = x;
    
    free(a);
    
    return tmp;
}

P top(priority_queue *a)
{
    return a->value;
}

int empty(priority_queue *a)
{
    if (a == NULL) {
        return 1;
    } else {
        return 0;
    }
}

void clear(priority_queue *a)
{
    if (a->left != NULL) clear(a->left);
    if (a->right != NULL) clear(a->right);
    
    free(a);
}

double maximum(double a, double b)
{
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

double a[250001];

int main()
{
    int n, m, i, j;
    char s[500][501];
    int f[500][500];
    priority_queue *q = NULL;
    
    scanf("%d %d", &n, &m);
    
    for (i = 0; i < n; i++) scanf("%s", s[i]);
    
    a[0] = 1;
    
    for (i = 1; i <= n * m; i++) a[i] = a[i - 1] * 0.99;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            f[i][j] = 0;
        }
    }
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (s[i][j] == 's') {
                q = push(q, make_tuple(-100, i * 500 + j, 0));
                
                break;
            }
        }
    }
    
    while (!empty(q)) {
        tuple t = top(q);
        int x, y, z;
        double c;
        
        q = pop(q);
        
        c = t.first;
        x = t.second / 500;
        y = (t.second - x * 500) % m;
        z = t.third + 1;
        
        if (s[x][y] == 'g') {
            printf("%.12lf\n", -c);
            
            return 0;
        }
        
        if (f[x][y] == 1) continue;
        
        f[x][y] = 1;
        
        if (x > 0 && s[x - 1][y] != '#' && f[x - 1][y] == 0) {
            if (s[x - 1][y] == 'g') {
                q = push(q, make_tuple(c, (x - 1) * 500 + y, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x - 1][y] - '0') * a[z]), (x - 1) * 500 + y, z));
            }
        }
        
        if (x < n - 1 && s[x + 1][y] != '#' && f[x + 1][y] == 0) {
            if (s[x + 1][y] == 'g') {
                q = push(q, make_tuple(c, (x + 1) * 500 + y, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x + 1][y] - '0') * a[z]), (x + 1) * 500 + y, z));
            }
        }
        
        if (y > 0 && s[x][y - 1] != '#' && f[x][y - 1] == 0) {
            if (s[x][y - 1] == 'g') {
                q = push(q, make_tuple(c, x * 500 + y - 1, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x][y - 1] - '0') * a[z]), x * 500 + y - 1, z));
            }
        }
        
        if (y < m - 1 && s[x][y + 1] != '#' && f[x][y + 1] == 0) {
            if (s[x][y + 1] == 'g') {
                q = push(q, make_tuple(c, x * 500 + y + 1, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x][y + 1] - '0') * a[z]), x * 500 + y + 1, z));
            }
        }
    }
    
    puts("-1");
    
    return 0;
}

Submission Info

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

Compile Error

./Main.c: In function ‘main’:
./Main.c:172: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
./Main.c:174: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 21
WA × 43
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 25 ms 688 KB
00_mini_02.txt AC 21 ms 664 KB
00_mini_03.txt AC 20 ms 732 KB
00_mini_04.txt AC 21 ms 672 KB
00_mini_05.txt AC 21 ms 668 KB
00_sample_01.txt AC 20 ms 668 KB
00_sample_02.txt AC 21 ms 668 KB
01_rnd_01.txt WA 226 ms 5372 KB
01_rnd_02.txt WA 38 ms 2936 KB
01_rnd_03.txt WA 23 ms 1156 KB
01_rnd_04.txt WA 28 ms 1784 KB
01_rnd_05.txt WA 22 ms 1044 KB
01_rnd_06.txt WA 21 ms 916 KB
01_rnd_07.txt WA 25 ms 1944 KB
01_rnd_08.txt WA 41 ms 3188 KB
01_rnd_09.txt WA 49 ms 3460 KB
01_rnd_10.txt WA 62 ms 3316 KB
01_rnd_11.txt WA 43 ms 2296 KB
01_rnd_12.txt WA 30 ms 1908 KB
01_rnd_13.txt WA 23 ms 920 KB
01_rnd_14.txt WA 59 ms 2680 KB
01_rnd_15.txt WA 39 ms 2036 KB
01_rnd_16.txt AC 23 ms 1564 KB
01_rnd_17.txt AC 34 ms 2036 KB
01_rnd_18.txt AC 21 ms 924 KB
01_rnd_19.txt AC 23 ms 1908 KB
01_rnd_20.txt AC 22 ms 1812 KB
02_maxrnd_01.txt WA 82 ms 4864 KB
02_maxrnd_02.txt WA 64 ms 4992 KB
02_maxrnd_03.txt WA 78 ms 4732 KB
02_maxrnd_04.txt WA 100 ms 5500 KB
02_maxrnd_05.txt WA 85 ms 4604 KB
02_maxrnd_06.txt WA 187 ms 4996 KB
02_maxrnd_07.txt WA 49 ms 4220 KB
02_maxrnd_08.txt WA 44 ms 3964 KB
02_maxrnd_09.txt WA 149 ms 4852 KB
02_maxrnd_10.txt WA 55 ms 4224 KB
02_maxrnd_11.txt WA 124 ms 4604 KB
02_maxrnd_12.txt WA 69 ms 4344 KB
02_maxrnd_13.txt WA 80 ms 4224 KB
02_maxrnd_14.txt WA 83 ms 4220 KB
02_maxrnd_15.txt WA 47 ms 3944 KB
02_maxrnd_16.txt WA 66 ms 3968 KB
02_maxrnd_17.txt WA 61 ms 3848 KB
02_maxrnd_18.txt AC 44 ms 3840 KB
02_maxrnd_19.txt AC 43 ms 3828 KB
03_hard_01.txt WA 252 ms 6856 KB
03_hard_02.txt WA 326 ms 7288 KB
03_hard_03.txt AC 62 ms 3828 KB
03_hard_04.txt AC 61 ms 3828 KB
03_hard_05.txt WA 246 ms 6268 KB
03_hard_06.txt WA 315 ms 6784 KB
03_hard_07.txt AC 62 ms 3836 KB
03_hard_08.txt AC 60 ms 3832 KB
04_open_01.txt AC 209 ms 3836 KB
04_open_02.txt WA 294 ms 5760 KB
05_minihard_01.txt WA 22 ms 792 KB
05_minihard_02.txt WA 21 ms 812 KB
05_minihard_03.txt AC 21 ms 784 KB
05_minihard_04.txt AC 21 ms 788 KB
05_minihard_05.txt WA 21 ms 792 KB
05_minihard_06.txt WA 22 ms 776 KB
05_minihard_07.txt WA 21 ms 744 KB
05_minihard_08.txt WA 21 ms 792 KB