Submission #669893


Source Code Expand

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

// 孤立点処理
// 孤立2点処理
// 湖畔を走る経路を優先するスコア
public class Main {
	static InputStream is;
	static PrintWriter out;
//	static String INPUT = "3 3 0 3 3 0 0 0 0";
	static String INPUT = "";
	
	static int hand;
	static int[] dr = { 1, 0, -1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int[] hist;
	static long maxscore = -1;
	static int[] argmaxhist;
	static boolean[][] ved;
	
	static void solve()
	{
		int n = 30;
		int[][] a = new int[n][];
		for(int i = 0;i < n;i++){
			a[i] = na(n);
		}
		
		hist = new int[120];
		int m = 0;
		ved = new boolean[n][n];
		while((m = max(a)) > 0){
			maxscore = -1;
			argmaxhist = null;
			
			// 孤立点に対する前処理
			if(processSolitaryCell(a))continue;
//			if(processSolitaryCell2(a))continue;
//			if(processSolitaryCell3(a))continue;
//			if(processSolitaryCell4(a))continue;
			
			// 孤立2点に対する前処理
			if(processSolitaryTwoCells(a))continue;
			
//			// 孤立3点に対する前処理
//			if(processSolitaryThreeCells(a))continue;
			
			for(int i = 0;i < n;i++){
				for(int j = 0;j < n;j++){
					if(a[i][j] == m){
						dfs(i, j, a[i][j], a, 0, 0, 0);
					}
				}
			}
			
			assert argmaxhist != null;
			int pre = -2;
			for(int v : argmaxhist){
				int r = v>>>6, c = v&63;
				if(pre == -2 || a[r][c] == pre-1){
					out.println((r+1) + " " + (c+1));
					pre = a[r][c];
					a[r][c]--;
				}else{
					break;
				}
			}
//			if(hand == 10000){
//				for(int[] row : a){
//					tr(row);
//				}
//			}
			hand++;
		}
//		tr(hand);
	}
	
	static boolean processSolitaryCell(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		for(int i = 0;i < n;i++){
			outer:
			for(int j = 0;j < n;j++){
				if(a[i][j] > 0){
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(Math.abs(a[nr][nc]-a[i][j]) == 1 || a[i][j] < a[nr][nc])continue outer;
						}
					}
					int[] as = new int[4];
					int p = 0;
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							as[p++] = a[nr][nc];
						}
					}
					if(p-2 >= 0){
						Arrays.sort(as, 0, p);
						if(as[p-1] == as[p-2] + 2 && a[i][j] >= as[p-1]){
							while(a[i][j] > as[p-1]-1){
								out.println((i+1) + " " + (j+1));
								a[i][j]--;
								processed = true;
								hand++;
							}
						}
					}
				}
			}
		}
		return processed;
	}
	
	static boolean processSolitaryCell4(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		for(int i = 0;i < n;i++){
			outer:
			for(int j = 0;j < n;j++){
				if(a[i][j] > 0){
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(Math.abs(a[nr][nc]-a[i][j]) == 1 || a[i][j] < a[nr][nc])continue outer;
						}
					}
					int[] as = new int[4];
					int p = 0;
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							as[p++] = a[nr][nc];
						}
					}
					if(p-2 >= 0){
						Arrays.sort(as, 0, p);
						if(Arrays.binarySearch(as, 0, p, as[p-1] - 2) >= 0 && a[i][j] >= as[p-1]){
							while(a[i][j] > as[p-1]){
								out.println((i+1) + " " + (j+1));
								a[i][j]--;
								processed = true;
								hand++;
							}
						}
					}
				}
			}
		}
		return processed;
	}
	
	static boolean processSolitaryCell2(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		for(int i = 0;i < n;i++){
			outer:
			for(int j = 0;j < n;j++){
				if(a[i][j] > 0){
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(Math.abs(a[nr][nc]-a[i][j]) == 1 || a[i][j] < a[nr][nc])continue outer;
						}
					}
					int[] as = new int[4];
					int p = 0;
					int okmax = -1;
					boolean ok = false;
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							for(int l = 0;l < 4;l++){
								int nnr = i + dr[l], nnc = j + dc[l];
								if(nnr >= 0 && nnr < n && nnc >= 0 && nnc < n && a[nnr][nnc] > 0){
									if(a[nr][nc] - a[nnr][nnc] == 2){
										int xr = i + dr[k] + dr[l], xc = j + dc[k] + dc[l];
										if(!(xr == i && xc == j) && a[xr][xc] == a[nr][nc] - 1){
											continue;
										}
										okmax = Math.max(okmax, a[nr][nc]);
									}
								}
							}
							as[p++] = a[nr][nc];
						}
					}
					Arrays.sort(as, 0, p);
					if(p-2 >= 0 && okmax > 0 && okmax == as[p-1] && as[p-1] == as[p-2] + 2 && a[i][j] >= as[p-1]){
						while(a[i][j] >= as[p-1]){
							out.println((i+1) + " " + (j+1));
							a[i][j]--;
							processed = true;
							hand++;
						}
					}
				}
			}
		}
		return processed;
	}
	
	static boolean processSolitaryCell3(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		
		int max = -1;
		int argmaxi = -1;
		int argmaxj = -1;
		for(int i = 0;i < n;i++){
			outer:
			for(int j = 0;j < n;j++){
				if(a[i][j] > 0){
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(Math.abs(a[nr][nc]-a[i][j]) == 1 || a[i][j] < a[nr][nc])continue outer;
						}
					}
					int[] as = new int[4];
					int p = 0;
					for(int k = 0;k < 4;k++){
						int nr = i + dr[k], nc = j + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							as[p++] = a[nr][nc];
						}
					}
					if(p-2 >= 0){
						Arrays.sort(as, 0, p);
						if(as[p-1] == as[p-2] + 2 && a[i][j] >= as[p-1]){
							if(as[p-1] > max){
								max = as[p-1];
								argmaxi = i;
								argmaxj = j;
							}
						}
					}
				}
			}
		}
		if(max > 0){
			int i = argmaxi, j = argmaxj;
			while(a[i][j] > max - 1){
				out.println((i+1) + " " + (j+1));
				a[i][j]--;
				processed = true;
				hand++;
			}
		}
		return processed;
	}
	
	
	static boolean processSolitaryTwoCells(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		for(int r = 0;r < n;r++){
			outer:
			for(int c = 0;c < n;c++){
				if(a[r][c] > 0){
					for(int k = 0;k < 4;k++){
						int nr = r + dr[k], nc = c + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(a[r][c] < a[nr][nc])continue outer;
						}
					}
					inner:
					for(int z = 0;z < 4;z++){
						int br = r + dr[z], bc = c + dc[z];
						if(br >= 0 && br < n && bc >= 0 && bc < n && a[br][bc] > 0){
							for(int k = 0;k < 4;k++){
								int nr = br + dr[k], nc = bc + dc[k];
								if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
									if(!(nr == r && nc == c) && a[br][bc] < a[nr][nc])continue inner;
								}
							}
							
							int maxa = -1;
							for(int k = 0;k < 4;k++){
								int nr = r + dr[k], nc = c + dc[k];
								if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0 && !(nr == br && nc == bc)){
									maxa = Math.max(maxa, a[nr][nc]);
								}
							}
							int maxb = -1;
							for(int k = 0;k < 4;k++){
								int nr = br + dr[k], nc = bc + dc[k];
								if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0 && !(nr == r && nc == c)){
									maxb = Math.max(maxb, a[nr][nc]);
								}
							}
							if(maxb > 0 && maxa - maxb == 3){
								int ta = maxa-1, tb = maxa-2;
								while(a[r][c] > ta && a[br][bc] > tb){
									if(a[r][c] > a[br][bc]+1){
										out.println((r+1) + " " + (c+1));
										a[r][c]--;
										processed = true;
										hand++;
									}else if(a[r][c] == a[br][bc]+1){
										out.println((r+1) + " " + (c+1));
										out.println((br+1) + " " + (bc+1));
										a[r][c]--;
										a[br][bc]--;
										processed = true;
										hand++;
									}else{
										out.println((br+1) + " " + (bc+1));
										a[br][bc]--;
										processed = true;
										hand++;
									}
								}
							}
						}
					}
				}
			}
		}
		return processed;
	}
	
	static boolean processSolitaryThreeCells(int[][] a)
	{
		boolean processed = false;
		int n = a.length;
		for(int ar = 0;ar < n;ar++){
			outer:
			for(int ac = 0;ac < n;ac++){
				if(a[ar][ac] > 0){
					for(int k = 0;k < 4;k++){
						int nr = ar + dr[k], nc = ac + dc[k];
						if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
							if(a[ar][ac] < a[nr][nc])continue outer;
						}
					}
					inner:
					for(int z = 0;z < 4;z++){
						int br = ar + dr[z], bc = ac + dc[z];
						if(br >= 0 && br < n && bc >= 0 && bc < n && a[br][bc] > 0){
							for(int k = 0;k < 4;k++){
								int nr = br + dr[k], nc = bc + dc[k];
								if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
									if(!(nr == ar && nc == ac) && a[br][bc] < a[nr][nc])continue inner;
								}
							}
							
							linner:
							for(int y = 0;y < 4;y++){
								int cr = br + dr[y], cc = bc + dc[y];
								if(cr >= 0 && cr < n && cc >= 0 && cc < n && a[cr][cc] > 0 && !(cr == ar && cc == ac)){
									for(int k = 0;k < 4;k++){
										int nr = cr + dr[k], nc = cc + dc[k];
										if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
											if(!(nr == br && nc == bc) && a[cr][cc] < a[nr][nc])continue linner;
										}
									}
									
									int maxa = -1;
									for(int k = 0;k < 4;k++){
										int nr = ar + dr[k], nc = ac + dc[k];
										if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0 && !(nr == br && nc == bc)){
											maxa = Math.max(maxa, a[nr][nc]);
										}
									}
									int maxc = -1;
									for(int k = 0;k < 4;k++){
										int nr = cr + dr[k], nc = cc + dc[k];
										if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0 && !(nr == br && nc == bc)){
											maxc = Math.max(maxc, a[nr][nc]);
										}
									}
									if(maxc > 0 && maxa - maxc == 4){
										int ta = maxa-1, tb = maxa-2, tc = maxa-3;
										while(a[ar][ac] > ta && a[br][bc] > tb && a[cr][cc] > tc){
											int ra = a[ar][ac]-ta;
											int rb = a[br][bc]-tb;
											int rc = a[cr][cc]-tc;
											int mr = Math.max(Math.max(ra, rb), rc);
											if(ra == mr){
												out.println((ar+1) + " " + (ac+1));
												a[ar][ac]--;
												hand++;
												processed = true;
											}
											if(rb == mr){
												out.println((br+1) + " " + (bc+1));
												a[br][bc]--;
												if(ra != mr)hand++;
												processed = true;
											}
											if(rc == mr){
												out.println((cr+1) + " " + (cc+1));
												a[cr][cc]--;
												if(rb != mr)hand++;
												processed = true;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return processed;
	}
	
	static void dfs(int r, int c, int v, int[][] a, long score, int dep, int start)
	{
		a[r][c]--;
		ved[r][c] = true;
		hist[dep] = r<<6|c;
		score += 1000000;
		
		int n = a.length;
		// 0以外とできるだけ接しないところを通るように
		for(int k = 0;k < 4;k++){
			int nr = r + dr[k], nc = c + dc[k];
			if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0){
				score -= a[nr][nc]*(dep*dep/4);
//				score -= a[nr][nc] * dep;//(dep/2);
//				score -= a[nr][nc];
			}
		}
		
//		tr(score, Arrays.copyOf(hist, dep+1));
		if(score > maxscore){
			maxscore = score;
			argmaxhist = Arrays.copyOfRange(hist, start, dep+1);
		}
		if(score + 1000000*v > maxscore){
			if(a[r][c] > 0 && v > 0){
				for(int k = 0;k < 4;k++){
					int nr = r + dr[k], nc = c + dc[k];
					if(nr >= 0 && nr < n && nc >= 0 && nc < n && a[nr][nc] > 0 && !ved[nr][nc]){
						if(a[nr][nc] >= a[r][c]){
							dfs(nr, nc, v-1, a, score-203000*(a[nr][nc]-a[r][c]), dep+1, a[nr][nc] > a[r][c] ? dep+1 : start);
						}
					}
				}
			}
		}
		ved[r][c] = false;
		a[r][c]++;
	}
	
	static int max(int[][] a)
	{
		int m = 0;
		for(int[] row : a){
			for(int v : row){
				m = Math.max(m, v);
			}
		}
		return m;
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User uwi
Language Java8 (OpenJDK 1.8.0)
Score 885517
Code Size 15813 Byte
Status AC
Exec Time 4468 ms
Memory 39840 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 88663 / 100000 88434 / 100000 88462 / 100000 88479 / 100000 88482 / 100000 88696 / 100000 88777 / 100000 88544 / 100000 88415 / 100000 88565 / 100000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 1960 ms 36000 KB
subtask_01_02.txt AC 1972 ms 23200 KB
subtask_01_03.txt AC 2179 ms 37916 KB
subtask_01_04.txt AC 1876 ms 30500 KB
subtask_01_05.txt AC 2191 ms 37204 KB
subtask_01_06.txt AC 2044 ms 33432 KB
subtask_01_07.txt AC 4468 ms 39840 KB
subtask_01_08.txt AC 2108 ms 33808 KB
subtask_01_09.txt AC 2163 ms 38348 KB
subtask_01_10.txt AC 2023 ms 29240 KB