Submission #1518277
Source Code Expand
import java.util.HashSet; import java.util.Scanner; import java.util.Set; /** * http://abc025.contest.atcoder.jp/tasks/abc025_d */ public class Main { static final int N = 5; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] f = new int[N][N]; Set<Integer> list = new HashSet<Integer>(); for(int i=1; i<=N*N; i++) list.add(i); for(int y=0; y<N; y++){ for(int x=0; x<N; x++){ f[y][x] = sc.nextInt(); list.remove(f[y][x]); } } sc.close(); System.out.println(getCount(f, list)); } static long getCount(int[][] f, Set<Integer> list) { if(list.isEmpty()){ return 1; } int result = 0; boolean find = false; for(int y=0; y<N; y++){ for(int x=0; x<N; x++){ if(f[y][x]==0){ find = true; for(int n:list){ int[][] f2 = getCopy(f); f2[y][x]=n; if(!check(f2,x,y)) continue; Set<Integer> list2 = new HashSet<Integer>(); for(int i:list) if(i!=n) list2.add(i); result += getCount(f2,list2); } break; } } if(find) break; } return result; } static boolean check(final int[][] f, final int px, final int py){ //System.out.println("------------------------"); //System.out.println(py+":" + px); //for(int y=0; y<N; y++) System.out.println(Arrays.toString(f[y])); for(int x=px-2; x<=px; x++){ if(x<0 || x+2>=N) continue; if(f[py][x+1]==0 || f[py][x+2]==0) continue; if(f[py][x]>f[py][x+1] && f[py][x+1]>f[py][x+2]) return false; if(f[py][x]<f[py][x+1] && f[py][x+1]<f[py][x+2]) return false; } for(int y=py-2; y<=py; y++){ if(y<0 || y+2>=N) continue; if(f[y+1][px]==0 || f[y+2][px]==0) continue; if(f[y][px]>f[y+1][px] && f[y+1][px]> f[y+2][px]) return false; if(f[y][px]<f[y+1][px] && f[y+1][px]< f[y+2][px]) return false; } return true; } static int[][] getCopy(int[][] f){ int[][] copy = new int[N][N]; for(int y=0; y<N; y++) for(int x=0; x<N; x++) copy[y][x] = f[y][x]; return copy; } }
Submission Info
Submission Time | |
---|---|
Task | D - 25個の整数 |
User | namayaki |
Language | Java8 (OpenJDK 1.8.0) |
Score | 30 |
Code Size | 2116 Byte |
Status | TLE |
Exec Time | 5263 ms |
Memory | 366528 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 70 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt |
Subtask2 | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 105 ms | 17620 KB |
sample-02.txt | AC | 226 ms | 51520 KB |
sample-03.txt | AC | 93 ms | 21204 KB |
sample-04.txt | AC | 104 ms | 21716 KB |
test-1-01.txt | AC | 93 ms | 19412 KB |
test-1-02.txt | AC | 93 ms | 18644 KB |
test-1-03.txt | AC | 110 ms | 19540 KB |
test-1-04.txt | AC | 105 ms | 20436 KB |
test-1-05.txt | AC | 115 ms | 24148 KB |
test-1-06.txt | AC | 129 ms | 27732 KB |
test-1-07.txt | AC | 93 ms | 17748 KB |
test-1-08.txt | AC | 116 ms | 24404 KB |
test-1-09.txt | AC | 113 ms | 19924 KB |
test-1-10.txt | AC | 92 ms | 20308 KB |
test-1-11.txt | AC | 95 ms | 21844 KB |
test-1-12.txt | AC | 109 ms | 22356 KB |
test-1-13.txt | AC | 91 ms | 19796 KB |
test-1-14.txt | AC | 111 ms | 21972 KB |
test-1-15.txt | AC | 127 ms | 22100 KB |
test-2-01.txt | TLE | 5259 ms | 364468 KB |
test-2-02.txt | TLE | 5259 ms | 357996 KB |
test-2-03.txt | MLE | 1999 ms | 246484 KB |
test-2-04.txt | TLE | 5259 ms | 365612 KB |
test-2-05.txt | TLE | 5259 ms | 252236 KB |
test-2-06.txt | TLE | 5263 ms | 355620 KB |
test-2-07.txt | TLE | 5259 ms | 366528 KB |
test-2-08.txt | TLE | 5259 ms | 358136 KB |
test-2-09.txt | TLE | 5263 ms | 359772 KB |
test-2-10.txt | TLE | 5263 ms | 363580 KB |