Contest Duration: - (local time) (90 minutes) Back to Home

Submission #19160

Source Code Expand

Copy
```import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
public static class State implements Comparable<State> {
int nx;
int ny;
int t;

public State(int x, int y, int _t) {
nx = x;
ny = y;
t = _t;
}

@Override
public int compareTo(State arg0) {
return t - arg0.t;
}
}

static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};

public static void main(String[] args) throws IOException {
int N = Integer.valueOf(sz[0]);
int M = Integer.valueOf(sz[1]);

int[][] data = new int[N+2][M+2];
int sx = 0, sy = 0;
int gx = 0, gy = 0;
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < M ; j++) {
if (line.charAt(j) == 's') {
data[i+1][j+1] = 11;
sx = j+1;
sy = i+1;
} else if (line.charAt(j) == 'g') {
data[i+1][j+1] = 12;
gx = j+1;
gy = i+1;
} else if (line.charAt(j) == '#') {
} else {
data[i+1][j+1] = line.charAt(j) - '0';
}
}
}

double[][] dvalue = new double[10][5001];
for (int v = 1 ; v <= 9 ; v++) {
dvalue[v][0] = v;
for (int t = 0 ; t < 5000 ; t++) {
dvalue[v][t+1] = dvalue[v][t] * 99 / 100;
}
}

int time = -1;
{
Queue<State> q = new PriorityQueue<State>();
boolean[][] visited = new boolean[N+2][M+2];
visited[sy][sx] = true;
while (q.size() >= 1) {
State stat = q.poll();
for (int d = 0 ; d < 4 ; d++) {
int tx = (stat.nx + dx[d]);
int ty = (stat.ny + dy[d]);
int tt = stat.t + 1;
int lightval = data[ty][tx];
if (lightval == 11 || lightval == 0) {
continue;
}
if (lightval == 12) {
time = tt;
break;
}
if (!visited[ty][tx]) {
visited[ty][tx] = true;
}
}
}
if (time == -1) {
System.out.println("-1");
return;
}
}

double max = 9.0d;
double min = 0.0d;
for (int cur = 0 ; cur < 300 ; cur++) {
double med = (max + min) / 2.0d;
if (Math.abs(min - med) < 10e-11) {
break;
}
double[][] maxl = new double[N+2][M+2];
for (int d = 0 ; d < N+2 ; d++) {
Arrays.fill(maxl[d], 0.0d);
}
Queue<State> q = new PriorityQueue<State>();
boolean isok = false;
search: while (q.size() >= 1) {
State stat = q.poll();
for (int d = 0 ; d < 4 ; d++) {
int tx = (stat.nx + dx[d]);
int ty = (stat.ny + dy[d]);
int tt = stat.t + 1;
if (data[ty][tx] == 0) {
continue;
}
if (tt >= 5000) {
continue;
}

int lightval = data[ty][tx];
if (lightval == 11) {
continue;
}
if (lightval == 12) {
isok = true;
break search;
}
if (dvalue[lightval][tt] < med) {
continue;
}
if (maxl[ty][tx] < dvalue[lightval][tt]) {
maxl[ty][tx] = dvalue[lightval][tt];
}
}
}
if (isok) {
min = med;
} else {
max = med;
}
}
System.out.println(min);
}
}```

#### Submission Info

Submission Time 2012-05-27 21:02:16+0900 C - 暗闇帰り道 hamadu Java (OpenJDK 1.7.0) 100 3469 Byte AC 2479 ms 51444 KB

#### Judge Result

Set Name all
Score / Max Score 100 / 100
Status
 AC × 64
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 469 ms 21500 KB
00_mini_02.txt AC 462 ms 22856 KB
00_mini_03.txt AC 438 ms 22740 KB
00_mini_04.txt AC 449 ms 22820 KB
00_mini_05.txt AC 435 ms 20644 KB
00_sample_01.txt AC 434 ms 22956 KB
00_sample_02.txt AC 453 ms 22784 KB
01_rnd_01.txt AC 2125 ms 47168 KB
01_rnd_02.txt AC 752 ms 33944 KB
01_rnd_03.txt AC 624 ms 37036 KB
01_rnd_04.txt AC 657 ms 34200 KB
01_rnd_05.txt AC 565 ms 28396 KB
01_rnd_06.txt AC 509 ms 27264 KB
01_rnd_07.txt AC 612 ms 36360 KB
01_rnd_08.txt AC 810 ms 33584 KB
01_rnd_09.txt AC 989 ms 38392 KB
01_rnd_10.txt AC 1124 ms 35696 KB
01_rnd_11.txt AC 834 ms 33332 KB
01_rnd_12.txt AC 745 ms 32800 KB
01_rnd_13.txt AC 653 ms 37116 KB
01_rnd_14.txt AC 1307 ms 35736 KB
01_rnd_15.txt AC 859 ms 33400 KB
01_rnd_16.txt AC 579 ms 34788 KB
01_rnd_17.txt AC 509 ms 25412 KB
01_rnd_18.txt AC 440 ms 23660 KB
01_rnd_19.txt AC 466 ms 23956 KB
01_rnd_20.txt AC 705 ms 23156 KB
02_maxrnd_01.txt AC 1021 ms 43644 KB
02_maxrnd_02.txt AC 884 ms 40400 KB
02_maxrnd_03.txt AC 1066 ms 43736 KB
02_maxrnd_04.txt AC 1461 ms 48640 KB
02_maxrnd_05.txt AC 1067 ms 42336 KB
02_maxrnd_06.txt AC 2213 ms 51012 KB
02_maxrnd_07.txt AC 757 ms 39216 KB
02_maxrnd_08.txt AC 696 ms 38028 KB
02_maxrnd_09.txt AC 2213 ms 50928 KB
02_maxrnd_10.txt AC 864 ms 38292 KB
02_maxrnd_11.txt AC 2027 ms 51264 KB
02_maxrnd_12.txt AC 1263 ms 48040 KB
02_maxrnd_13.txt AC 1503 ms 47928 KB
02_maxrnd_14.txt AC 1649 ms 49572 KB
02_maxrnd_15.txt AC 790 ms 35556 KB
02_maxrnd_16.txt AC 1358 ms 45688 KB
02_maxrnd_17.txt AC 1106 ms 45924 KB
02_maxrnd_18.txt AC 517 ms 25880 KB
02_maxrnd_19.txt AC 483 ms 25724 KB
03_hard_01.txt AC 2255 ms 50560 KB
03_hard_02.txt AC 2333 ms 50944 KB
03_hard_03.txt AC 610 ms 38192 KB
03_hard_04.txt AC 660 ms 40596 KB
03_hard_05.txt AC 2271 ms 50860 KB
03_hard_06.txt AC 2328 ms 50892 KB
03_hard_07.txt AC 607 ms 38576 KB
03_hard_08.txt AC 624 ms 36804 KB
04_open_01.txt AC 2479 ms 51116 KB
04_open_02.txt AC 2412 ms 51444 KB
05_minihard_01.txt AC 513 ms 26164 KB
05_minihard_02.txt AC 500 ms 27796 KB
05_minihard_03.txt AC 492 ms 27108 KB
05_minihard_04.txt AC 511 ms 27788 KB
05_minihard_05.txt AC 512 ms 25760 KB
05_minihard_06.txt AC 496 ms 26288 KB
05_minihard_07.txt AC 502 ms 28020 KB
05_minihard_08.txt AC 501 ms 28696 KB