Submission #18729


Source Code Expand

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] sz = s.readLine().split(" ");
		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++) {
			String line = s.readLine();
			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][25001];
		for (int v = 1 ; v <= 9 ; v++) {
			dvalue[v][0] = v;
			for (int t = 0 ; t < 25000 ; t++) {
				dvalue[v][t+1] = dvalue[v][t] * 99 / 100; 
			}
		}
		
		
		double max = 9.0d;
		double min = 0.0d;
		boolean reached = false;
		for (int cur = 0 ; cur < 200 ; cur++) {
			double med = (max + min) / 2.0d;
			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>();
			q.add(new State(sx, sy, 0));
			boolean isok = false;
			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;
					}
					int lightval = data[ty][tx];
					if (lightval == 11) {
						continue;
					}
					if (lightval == 12) {
						isok = true;
						break;
					}
					
					if (dvalue[lightval][tt] < med) {
						continue;
					}
					if (maxl[ty][tx] < dvalue[lightval][tt]) {
						maxl[ty][tx] = dvalue[lightval][tt];
						q.add(new State(tx, ty, tt));
					}
				}
			}
			if (isok) {
				reached = true;
				min = med;
			} else {
				max = med;
			}
		}
		
		if (reached) {
			System.out.println(min);
		} else {
			System.out.println("-1");
		}
	}
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User hamadu
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 2731 Byte
Status TLE
Exec Time 5088 ms
Memory 52332 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 45
WA × 4
TLE × 14
RE × 1
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 563 ms 23240 KB
00_mini_02.txt AC 482 ms 23248 KB
00_mini_03.txt AC 446 ms 23244 KB
00_mini_04.txt AC 433 ms 23224 KB
00_mini_05.txt AC 420 ms 23032 KB
00_sample_01.txt AC 439 ms 23228 KB
00_sample_02.txt AC 533 ms 23368 KB
01_rnd_01.txt TLE 5042 ms 50844 KB
01_rnd_02.txt AC 1604 ms 35160 KB
01_rnd_03.txt AC 645 ms 36732 KB
01_rnd_04.txt AC 1143 ms 34872 KB
01_rnd_05.txt AC 630 ms 33636 KB
01_rnd_06.txt AC 507 ms 33308 KB
01_rnd_07.txt AC 653 ms 34056 KB
01_rnd_08.txt AC 2108 ms 37276 KB
01_rnd_09.txt AC 2994 ms 49552 KB
01_rnd_10.txt AC 3847 ms 47296 KB
01_rnd_11.txt AC 2139 ms 35748 KB
01_rnd_12.txt AC 1695 ms 35376 KB
01_rnd_13.txt AC 863 ms 40548 KB
01_rnd_14.txt TLE 5042 ms 48984 KB
01_rnd_15.txt AC 2401 ms 35660 KB
01_rnd_16.txt AC 643 ms 34616 KB
01_rnd_17.txt AC 2335 ms 34196 KB
01_rnd_18.txt AC 498 ms 35640 KB
01_rnd_19.txt AC 521 ms 33880 KB
01_rnd_20.txt AC 566 ms 35592 KB
02_maxrnd_01.txt AC 2985 ms 51724 KB
02_maxrnd_02.txt AC 2346 ms 51340 KB
02_maxrnd_03.txt AC 3305 ms 51152 KB
02_maxrnd_04.txt TLE 5049 ms 52224 KB
02_maxrnd_05.txt AC 3355 ms 51372 KB
02_maxrnd_06.txt TLE 5043 ms 51484 KB
02_maxrnd_07.txt AC 1433 ms 51208 KB
02_maxrnd_08.txt AC 1136 ms 51432 KB
02_maxrnd_09.txt TLE 5088 ms 51524 KB
02_maxrnd_10.txt AC 1941 ms 51320 KB
02_maxrnd_11.txt TLE 5041 ms 51660 KB
02_maxrnd_12.txt AC 4712 ms 51620 KB
02_maxrnd_13.txt RE 0 ms 51192 KB
02_maxrnd_14.txt TLE 5041 ms 52108 KB
02_maxrnd_15.txt AC 1601 ms 50900 KB
02_maxrnd_16.txt TLE 5042 ms 51884 KB
02_maxrnd_17.txt AC 4586 ms 52208 KB
02_maxrnd_18.txt AC 988 ms 50500 KB
02_maxrnd_19.txt AC 889 ms 50984 KB
03_hard_01.txt TLE 5044 ms 51276 KB
03_hard_02.txt TLE 5041 ms 51668 KB
03_hard_03.txt WA 945 ms 51016 KB
03_hard_04.txt WA 992 ms 50720 KB
03_hard_05.txt TLE 5041 ms 52332 KB
03_hard_06.txt TLE 5043 ms 51020 KB
03_hard_07.txt WA 944 ms 50848 KB
03_hard_08.txt WA 1026 ms 50996 KB
04_open_01.txt TLE 5042 ms 51460 KB
04_open_02.txt TLE 5046 ms 51996 KB
05_minihard_01.txt AC 511 ms 30020 KB
05_minihard_02.txt AC 529 ms 28660 KB
05_minihard_03.txt AC 501 ms 28668 KB
05_minihard_04.txt AC 493 ms 29220 KB
05_minihard_05.txt AC 499 ms 29852 KB
05_minihard_06.txt AC 511 ms 30636 KB
05_minihard_07.txt AC 476 ms 28852 KB
05_minihard_08.txt AC 504 ms 30264 KB