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
AC × 4
AC × 19
AC × 19
TLE × 9
MLE × 1
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