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