Submission #1175563
Source Code Expand
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.security.SecureRandom;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Scanner;
public class Main {
public static int h;
public static int w;
public static int n;
public static int t;
public static Car[] car;
static int[] DI = {0,0,-1,1,0};
static int[] DJ = {-1,1,0,0,0};
static String LRUD = "LRUD-";
public static void main(String[] args) throws Exception {
solve(new IO());
//test();
}
public static void test() throws Exception {
Random r = new Random();
long seed = r.nextLong();
TestCase tc = new TestCase(seed);
String fileName = LocalDateTime.now().format(DateTimeFormatter.ofPattern("HHmmssSSS")) + "_" + seed;
PrintWriter pw = new PrintWriter(fileName+".txt");
pw.println(tc);
pw.close();
double score = solve(new IO(new FileInputStream(fileName+".txt"), new FileOutputStream(fileName+".out")));
System.err.println(score);
}
public static void input(IO io) throws Exception {
h = io.nextInt();
w = io.nextInt();
n = io.nextInt();
t = io.nextInt();
car = new Car[n];
for(int i=0;i<n;i++) {
int ci = io.nextInt() - 1;
int cj = io.nextInt() - 1;
int gi = io.nextInt() - 1;
int gj = io.nextInt() - 1;
car[i] = new Car(i,ci,cj,gi,gj);
}
}
public static double solve(IO io) throws Exception {
input(io);
ArrayList<String> ans = new ArrayList<>();
@SuppressWarnings("unchecked")
ArrayList<Car>[] stack = new ArrayList[h];
for(int i=0;i<h;i++) {
stack[i] = new ArrayList<>();
}
for(Car c: car) {
stack[c.gi].add(c);
}
for(int i=0;i<h;i++) {
stack[i].sort((c1,c2)->Integer.compare(c1.gj, c2.gj));
for(int j=0;j<stack[i].size();j++) {
Car c = stack[i].get(j);
c.si = i;
c.sj = j;
}
}
int phase = 0;
int[] completed = new int[h];
Arrays.fill(completed, -1);
for(int t=0;t<10000;t++) {
if (phase == 0) {
int constructMax = 12345;
for(int i=0;i<h;i++) {
if (completed[i] != stack[i].size() - 1) {
constructMax = Math.min(constructMax, completed[i] + 3);
}
}
constructMax = 999;
ans.add(step(completed,0.0,constructMax));
for(int i=0;i<h;i++) {
completed[i] = -1;
for(int j=0;j<stack[i].size();j++) {
Car c = stack[i].get(j);
if (c.i == i && c.j == j) {
completed[i] = j;
}else{
break;
}
}
}
boolean allDone = true;
for(int i=0;i<h;i++) {
if (completed[i] != stack[i].size() - 1) {
allDone = false;
break;
}
}
if (allDone) {
phase = 1;
}
continue;
}
if (phase == 1) {
boolean finish = true;
char[] move = new char[n];
for(int i=0;i<h;i++) {
for(int j=0;j<stack[i].size();j++) {
Car c = stack[i].get(j);
if (c.j < c.gj && (j == stack[i].size() - 1 || stack[i].get(j+1).j != c.j + 1)) {
c.j++;
move[c.id] = 'R';
finish = false;
}else{
move[c.id] = '-';
}
}
}
ans.add(String.valueOf(move));
if (finish) {
break;
}
continue;
}
}
io.println(ans.size());
for(String s:ans) {
io.println(s);
}
io.flush();
io.close();
return currentScore(car, ans.size());
}
public static String step(int[] completed, double random, int constructMax) {
char[] moves = new char[n];
boolean[][] occupied = new boolean[h][w];
for(Car c: car) {
occupied[c.i][c.j] = true;
}
ArrayList<Car> carList = new ArrayList<>();
for(Car c: car) {
carList.add(c);
}
Collections.shuffle(carList);
int completedMax = 0;
for(int i=0;i<h;i++) {
completedMax = Math.max(completed[i], completedMax);
}
for(Car c: carList) {
if (c.sj <= completed[c.si] && c.i == c.si && c.j == c.sj && completed[c.si] < constructMax) {
moves[c.id] = '-';
continue;
}
// int cd = dist2(c, c.i, c.j, completed, completedMax, completedAvg);
int kmax = 4;
int bestDist = Integer.MAX_VALUE;
ArrayList<Integer> allMove = new ArrayList<>();
ArrayList<Integer> goodMove = new ArrayList<>();
for(int k=0;k<kmax;k++) {
int ni = c.i + DI[k];
int nj = c.j + DJ[k];
if (ni < 0 || ni >= h || nj < 0 || nj >= w) {
continue;
}
if (occupied[ni][nj] && k != 4) {
continue;
}
int nd = dist2(c, ni, nj, completed, completedMax, constructMax);
if (nd < bestDist) {
goodMove.clear();
goodMove.add(k);
bestDist = nd;
}else if(nd == bestDist) {
goodMove.add(k);
}
allMove.add(k);
}
int move = 4;
if (!allMove.isEmpty()) {
if (Math.random() < random) {
move = allMove.get(randInt(0, allMove.size()-1));
}else{
move = goodMove.get(randInt(0, goodMove.size()-1));
}
}
c.i += DI[move];
c.j += DJ[move];
occupied[c.i][c.j] = true;
moves[c.id] = LRUD.charAt(move);
}
return String.valueOf(moves);
}
public static int dist2(Car c, int i,int j, int[] completed, int completedMax, int constructMax) {
int nd;
if (completed[c.si] + 1 == c.sj && completed[c.si] < constructMax) {
if (Math.abs(i - c.si) > 1) {
nd = 100 + dist(i,j,c.si,completedMax + 1);
}else{
nd = dist(i,j,c.si,c.sj);
}
}else{
nd = Math.max(0, completedMax + 2 - j);
}
return nd;
}
public static double currentScore(Car[] car, int t) {
double pt = 10 + t * 0.01;
double pd = 20;
for(Car c: car) {
pd += dist(c.i,c.j,c.gi,c.gj);
}
return 10000000 / (pd * pt);
}
public static int dist(int i,int j,int gi,int gj) {
return Math.abs(i - gi) + Math.abs(j - gj);
}
public static int randInt(int min,int max) {
return (int) (Math.random() * (max - min + 1)) + min;
}
}
class Car {
int id;
int i,j;
int gi,gj;
int si,sj;
public Car(int id,int i, int j, int gi, int gj) {
super();
this.id = id;
this.i = i;
this.j = j;
this.gi = gi;
this.gj = gj;
}
public Car copy() {
return new Car(id, i, j, gi, gj);
}
@Override
public String toString() {
return "(" + i + "," + j + ")" + "(" + si + "," + sj + ")";
}
}
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 in, OutputStream out) { super(out); this.in = in;}
public IO(InputStream source) { super(System.out); this.in = source;}
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) {}}
}
class TestCase {
static final int MIN_SIZE = 30;
static final int MAX_SIZE = 30;
static final int MIN_T = 10000;
static final int MAX_T = 10000;
static final double MIN_RATIO_K = 0.5;
static final double MAX_RATIO_K = 0.5;
SecureRandom rnd;
int H, W, K, T;
int[] A, B, C, D;
TestCase(long seed) throws Exception {
rnd = SecureRandom.getInstance("SHA1PRNG");
rnd.setSeed(seed);
this.H = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
this.W = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
double ratioK = rnd.nextDouble() * (MAX_RATIO_K - MIN_RATIO_K) + MIN_RATIO_K;
this.K = (int) Math.ceil(this.H * this.W * ratioK);
this.T = rnd.nextInt(MAX_T - MIN_T + 1) + MIN_T;
this.A = new int[K];
this.B = new int[K];
this.C = new int[K];
this.D = new int[K];
int[] pos = new int[H * W];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
pos[i * W + j] = (i << 16) | j;
}
}
shuffle(pos);
for (int i = 0; i < K; i++) {
this.A[i] = (pos[i] & 0xFFFF) + 1;
this.B[i] = (pos[i] >> 16) + 1;
}
shuffle(pos);
for (int i = 0; i < K; i++) {
this.C[i] = (pos[i] & 0xFFFF) + 1;
this.D[i] = (pos[i] >> 16) + 1;
}
}
private void shuffle(int[] ar) {
for (int i = 0; i < ar.length; i++) {
int to = rnd.nextInt(ar.length - i) + i;
int tmp = ar[i];
ar[i] = ar[to];
ar[to] = tmp;
}
}
TestCase(Scanner sc) throws Exception {
this.H = sc.nextInt();
this.W = sc.nextInt();
this.K = sc.nextInt();
this.T = sc.nextInt();
this.A = new int[K];
this.B = new int[K];
this.C = new int[K];
this.D = new int[K];
for (int i = 0; i < this.K; i++) {
this.A[i] = sc.nextInt();
this.B[i] = sc.nextInt();
this.C[i] = sc.nextInt();
this.D[i] = sc.nextInt();
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(this.H + " " + this.W + " " + this.K + " " + this.T + "\n");
for (int i = 0; i < K; ++i) {
builder.append(this.A[i] + " " + this.B[i] + " " + this.C[i] + " " + this.D[i] + "\n");
}
return builder.toString();
}
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
piroz95 |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
497412 |
Code Size |
12891 Byte |
Status |
AC |
Exec Time |
1122 ms |
Memory |
103184 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 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
Score / Max Score |
20400 / 50000 |
20049 / 50000 |
20425 / 50000 |
20956 / 50000 |
20653 / 50000 |
19593 / 50000 |
21562 / 50000 |
20877 / 50000 |
20334 / 50000 |
27 / 50000 |
20808 / 50000 |
20577 / 50000 |
20611 / 50000 |
20860 / 50000 |
27 / 50000 |
21089 / 50000 |
21277 / 50000 |
21295 / 50000 |
26 / 50000 |
20653 / 50000 |
21332 / 50000 |
27 / 50000 |
19842 / 50000 |
20628 / 50000 |
21515 / 50000 |
27 / 50000 |
29 / 50000 |
20869 / 50000 |
20450 / 50000 |
20594 / 50000 |
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 |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
562 ms |
46708 KB |
subtask_01_02.txt |
AC |
587 ms |
48264 KB |
subtask_01_03.txt |
AC |
527 ms |
59688 KB |
subtask_01_04.txt |
AC |
533 ms |
51212 KB |
subtask_01_05.txt |
AC |
535 ms |
49180 KB |
subtask_01_06.txt |
AC |
578 ms |
50624 KB |
subtask_01_07.txt |
AC |
572 ms |
51212 KB |
subtask_01_08.txt |
AC |
487 ms |
63764 KB |
subtask_01_09.txt |
AC |
497 ms |
48956 KB |
subtask_01_10.txt |
AC |
750 ms |
90440 KB |
subtask_01_11.txt |
AC |
548 ms |
50432 KB |
subtask_01_12.txt |
AC |
493 ms |
49476 KB |
subtask_01_13.txt |
AC |
498 ms |
64308 KB |
subtask_01_14.txt |
AC |
547 ms |
49436 KB |
subtask_01_15.txt |
AC |
1122 ms |
95864 KB |
subtask_01_16.txt |
AC |
534 ms |
50788 KB |
subtask_01_17.txt |
AC |
485 ms |
51068 KB |
subtask_01_18.txt |
AC |
493 ms |
58180 KB |
subtask_01_19.txt |
AC |
1060 ms |
97200 KB |
subtask_01_20.txt |
AC |
535 ms |
49088 KB |
subtask_01_21.txt |
AC |
508 ms |
49916 KB |
subtask_01_22.txt |
AC |
768 ms |
90244 KB |
subtask_01_23.txt |
AC |
514 ms |
49380 KB |
subtask_01_24.txt |
AC |
566 ms |
51040 KB |
subtask_01_25.txt |
AC |
473 ms |
49168 KB |
subtask_01_26.txt |
AC |
773 ms |
103184 KB |
subtask_01_27.txt |
AC |
719 ms |
75840 KB |
subtask_01_28.txt |
AC |
494 ms |
48540 KB |
subtask_01_29.txt |
AC |
507 ms |
51992 KB |
subtask_01_30.txt |
AC |
513 ms |
59916 KB |