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 |
|
|
|
|
|
|
|
|
|
|
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 |