Submission #1175399
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.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-";
@SuppressWarnings("unchecked")
public static ArrayList<Integer>[] temp = new ArrayList[4];
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 ALPHA = 0.00;
public static int FREEZE1 = 100;
public static int FREEZE2 = 10;
public static double solve(IO io) throws Exception {
input(io);
for(int i=0;i<4;i++) {
temp[i] = new ArrayList<>();
}
ArrayList<String> ans = new ArrayList<>();
int distSumMin = Integer.MAX_VALUE;
int freeze = 0;
int phase = 0;
for(int t=0;t<10000;t++) {
int distSum = 0;
for(Car c: car) {
distSum += dist(c.i,c.j,c.gi,c.gj);
}
if (distSum < distSumMin) {
freeze = 0;
distSumMin = distSum;
}else{
freeze++;
if (freeze > FREEZE1 && phase == 0) {
freeze = 0;
phase = 1;
}
if (freeze > FREEZE2 && phase == 1) {
break;
}
}
//System.err.println(currentScore(car, t));
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);
for(Car c: carList) {
for(ArrayList<Integer> al: temp) {
al.clear();
}
int cd = dist(c.i,c.j,c.gi,c.gj);
int kmax = phase == 0 ? 4 : 5;
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 = dist(ni,nj,c.gi,c.gj);
temp[cd-nd+1].add(k);
temp[3].add(k);
}
int move = 4;
if (!temp[3].isEmpty()) {
if (Math.random() < ALPHA) {
move = temp[3].get(randInt(0, temp[3].size()-1));
}else{
for(int i=0;i<3;i++) {
if (!temp[i].isEmpty()) {
move = temp[i].get(randInt(0,temp[i].size()-1));
}
}
}
}
c.i += DI[move];
c.j += DJ[move];
occupied[c.i][c.j] = true;
moves[c.id] = LRUD.charAt(move);
}
ans.add(String.valueOf(moves));
}
io.println(ans.size());
for(String s:ans) {
io.println(s);
}
io.flush();
io.close();
return currentScore(car, ans.size());
}
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;
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;
}
}
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 |
67017 |
Code Size |
10848 Byte |
Status |
AC |
Exec Time |
615 ms |
Memory |
39788 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 |
2398 / 50000 |
2585 / 50000 |
2557 / 50000 |
1974 / 50000 |
1981 / 50000 |
2542 / 50000 |
2048 / 50000 |
1914 / 50000 |
1949 / 50000 |
1959 / 50000 |
2349 / 50000 |
2920 / 50000 |
2610 / 50000 |
2305 / 50000 |
2406 / 50000 |
2665 / 50000 |
2475 / 50000 |
2096 / 50000 |
1955 / 50000 |
2529 / 50000 |
1845 / 50000 |
2510 / 50000 |
2587 / 50000 |
2191 / 50000 |
1722 / 50000 |
2023 / 50000 |
2224 / 50000 |
1839 / 50000 |
1743 / 50000 |
2116 / 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 |
309 ms |
35196 KB |
subtask_01_02.txt |
AC |
312 ms |
33836 KB |
subtask_01_03.txt |
AC |
456 ms |
37044 KB |
subtask_01_04.txt |
AC |
312 ms |
34436 KB |
subtask_01_05.txt |
AC |
420 ms |
37628 KB |
subtask_01_06.txt |
AC |
327 ms |
39256 KB |
subtask_01_07.txt |
AC |
362 ms |
37808 KB |
subtask_01_08.txt |
AC |
316 ms |
33744 KB |
subtask_01_09.txt |
AC |
324 ms |
36404 KB |
subtask_01_10.txt |
AC |
342 ms |
39228 KB |
subtask_01_11.txt |
AC |
427 ms |
39296 KB |
subtask_01_12.txt |
AC |
323 ms |
37248 KB |
subtask_01_13.txt |
AC |
317 ms |
35224 KB |
subtask_01_14.txt |
AC |
338 ms |
37920 KB |
subtask_01_15.txt |
AC |
480 ms |
37360 KB |
subtask_01_16.txt |
AC |
367 ms |
38028 KB |
subtask_01_17.txt |
AC |
338 ms |
37768 KB |
subtask_01_18.txt |
AC |
326 ms |
36248 KB |
subtask_01_19.txt |
AC |
353 ms |
38712 KB |
subtask_01_20.txt |
AC |
314 ms |
38896 KB |
subtask_01_21.txt |
AC |
340 ms |
37400 KB |
subtask_01_22.txt |
AC |
335 ms |
38288 KB |
subtask_01_23.txt |
AC |
326 ms |
35788 KB |
subtask_01_24.txt |
AC |
368 ms |
39788 KB |
subtask_01_25.txt |
AC |
374 ms |
38220 KB |
subtask_01_26.txt |
AC |
615 ms |
38248 KB |
subtask_01_27.txt |
AC |
390 ms |
38180 KB |
subtask_01_28.txt |
AC |
346 ms |
36348 KB |
subtask_01_29.txt |
AC |
327 ms |
37628 KB |
subtask_01_30.txt |
AC |
310 ms |
36400 KB |