Submission #2084699


Source Code Expand

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Main {
	public static final int H = 50;
	public static final int W = 50;
	public static final int K = 8;
	public static final int[] DI = {0,-1,0,1};
	public static final int[] DJ = {1,0,-1,0};
	public static final long TIME_MS = 9400;

	public static void main(String[] args) throws Exception {
		int n = 0;
		if (n <= 0) {
			solve(new IO());
		} else {
			for (int i = 1; i <= n; i++) {
				solve(new IO(String.format("A%02d", i),String.format("A%02d", i) + "_" + TIME_MS));
			}
		}
	}
	
	public static void solve(IO io) throws Exception {
		long stime = System.nanoTime();
		io.nextInt();
		io.nextInt();
		io.nextInt();
		int[][] a = new int[H][W];
		for(int i=0;i<H;i++) {
			char[] s = io.nextCharArray(W);
			for(int j=0;j<W;j++) {
				a[i][j] = s[j] - '0';
			}
		}
		
		ArrayList<Future<Result>> results = new ArrayList<>();
		ExecutorService executor = Executors.newFixedThreadPool(1);
		for(int i=0;i<4;i++) {
			results.add(executor.submit(() -> {
				Result best = null;
				while(System.nanoTime() - stime < TIME_MS * 1_000_000) {
					Result res = solve(a);
					if (best == null || res.score > best.score) {
						best = res;
					}
				}
				return best;
			}));
		}
		
		Result best = null;
		for(Future<Result> f: results) {
			Result r = f.get();
			if (best == null || r.score > best.score) {
				best = r;
			}
		}
		
		io.println(best.pieces.size());
		for(ArrayList<Integer> piece: best.pieces) {
			for(int p: piece) {
				io.println(((p >> 8 & 0xff) + 1) + " " + ((p & 0xff) + 1));
			}
		}
//		System.err.println(best.score);
		io.flush();
		
		executor.shutdown();
	}
	
	
	
	public static Result solve(int[][] a) {
		ArrayList<ArrayList<Integer>> pieces = new ArrayList<>();
		long score = 0;
		boolean[][] used = new boolean[H][W];
		for(int i=0;i<H;i++) {
			Arrays.fill(used[i], true);
		}
		for(int limit=9;limit>=1;limit--) {
			for(int i=0;i<H;i++) {
				for(int j=0;j<W;j++) {
					if (a[i][j] == limit) {
						used[i][j] = false;
					}
				}
			}
			ArrayList<Integer> al = new ArrayList<>();
			for(int i=0;i<H;i++) {
				for(int j=0;j<W;j++) {
					if (!used[i][j]) {
						al.add(encode(a[i][j],i,j));
					}
				}
			}
			Collections.shuffle(al);
			al.sort(PieceComp);
			for(int x: al) {
				int si = x >> 8 & 0xff;
				int sj = x & 0xff;
				if (used[si][sj] || a[si][sj] == 0) continue;
				ArrayList<Integer> piece = new ArrayList<>();
				int pieceScore = 1;
				PriorityQueue<Integer> q = new PriorityQueue<>(PieceComp);
				q.offer(x);
				while(!q.isEmpty() && piece.size() < K) {
					int p = q.poll();
					int ci = p >> 8 & 0xff;
					int cj = p & 0xff;
					int cn = p >> 16 & 0xff;
					if (used[ci][cj]) continue;
					piece.add(p);
					pieceScore *= cn;
					used[ci][cj] = true;
					if (piece.size() == K) {
						break;
					}
					for(int d=0;d<4;d++) {
						int ni = ci + DI[d];
						int nj = cj + DJ[d];
						if (ni < 0 || ni >= H || nj < 0 || nj >= W || used[ni][nj] || a[ni][nj] == 0) {
							continue;
						}
						q.offer(encode(a[ni][nj],ni,nj));
					}
				}
				if (piece.size() == K) {
					score += pieceScore;
					pieces.add(piece);
				}else{
					for(int p:piece) {
						used[p >> 8 & 0xff][p & 0xff] = false;
					}
				}
			}
		}
		return new Result(pieces, score);
	}
	
	public static final Comparator<Integer> PieceComp = (p1,p2) -> -Integer.compare(p1 >> 16, p2 >> 16);
	
	public static int encode(int a,int i,int j) {
		return a << 16 | i << 8 | j;
	}
}
class Result {
	ArrayList<ArrayList<Integer>> pieces;
	long score;
	public Result(ArrayList<ArrayList<Integer>> pieces, long score) {
		super();
		this.pieces = pieces;
		this.score = score;
	}
}
class IO extends PrintWriter {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	public IO() { this(System.in);}
	public IO(InputStream source) { super(System.out); this.in = source;}
	public IO(String fileName) throws IOException {
		super(new FileOutputStream(fileName + ".out"), false);
		this.in = new FileInputStream(new File(fileName + ".txt"));
	}
	public IO(String in,String out) throws IOException {
		super(new FileOutputStream(out + ".out"), false);
		this.in = new FileInputStream(new File(in + ".txt"));
	}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public char[] nextCharArray(int len) {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		char[] s = new char[len];
		int i = 0;
		int b = readByte();
		while(isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}
	public String nextLine() {
		if (!hasNextLine()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(!isNewLine(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public char nextChar() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		return (char) readByte();
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
	public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
	public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
	public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
	public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
	public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
	public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}

Submission Info

Submission Time
Task A - Multiple Pieces
User piroz95
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 8283 Byte
Status TLE
Exec Time 10510 ms
Memory 282520 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 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058 0 / 1343058
Status
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 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 TLE 10509 ms 231140 KB
subtask_01_02.txt TLE 10509 ms 234888 KB
subtask_01_03.txt TLE 10509 ms 232156 KB
subtask_01_04.txt TLE 10509 ms 282520 KB
subtask_01_05.txt TLE 10509 ms 162924 KB
subtask_01_06.txt TLE 10510 ms 230428 KB
subtask_01_07.txt TLE 10510 ms 230344 KB
subtask_01_08.txt TLE 10510 ms 231984 KB
subtask_01_09.txt TLE 10509 ms 158732 KB
subtask_01_10.txt TLE 10506 ms 163328 KB