Submission #2415191
Source Code Expand
Copy
import java.lang.Math; import java.util.Scanner; import java.util.Map; import java.util.HashMap; import java.util.Arrays; class Pair { public final int x; public final int y; public Pair(int x, int y) { this.x = x; this.y = y; } } class Main { static Map<Integer, Pair> map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int H = sc.nextInt(); int W = sc.nextInt(); int D = sc.nextInt(); map = new HashMap<>(); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { map.put(sc.nextInt(), new Pair(i, j)); } } // 累積和 long costs[][] = new long[D][H*W/D+1]; for (int i = 0; i < D; i++) { costs[i][0] = 0; for (int j = 1; j < H*W/D+1; j++) { costs[i][j] = costs[i][j-1] + singleHopCost(i+(j-1)*D, i+j*D); } // System.out.println(Arrays.toString(costs[i])); } int Q = sc.nextInt(); for (int q = 0; q < Q; q++) { int START = sc.nextInt(); int GOAL = sc.nextInt(); int lg = Math.max(START, GOAL); int sm = Math.min(START, GOAL); // System.out.println(Arrays.toString(costs[0])); long answer = costs[lg%D][lg/D] - costs[lg%D][sm/D]; // lg%D == sm%D System.out.println(answer); } } public static Integer singleHopCost(int l, int r) { if (l == 0) { return 0; } Pair lPoint = map.get(l); Pair rPoint = map.get(r); if (lPoint == null || rPoint == null) { return 0; } return Math.abs(lPoint.x - rPoint.x) + Math.abs(lPoint.y - rPoint.y); } }
Submission Info
Submission Time | |
---|---|
Task | D - Practical Skill Test |
User | osyoyu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 1840 Byte |
Status | AC |
Exec Time | 1266 ms |
Memory | 107604 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 1249 ms | 102056 KB |
02.txt | AC | 1190 ms | 96512 KB |
03.txt | AC | 1038 ms | 41632 KB |
04.txt | AC | 1188 ms | 98872 KB |
05.txt | AC | 1266 ms | 107604 KB |
06.txt | AC | 1232 ms | 104428 KB |
07.txt | AC | 1240 ms | 101292 KB |
08.txt | AC | 96 ms | 19668 KB |
09.txt | AC | 1179 ms | 103452 KB |
sample_01.txt | AC | 93 ms | 21844 KB |
sample_02.txt | AC | 95 ms | 21332 KB |
sample_03.txt | AC | 105 ms | 20692 KB |