Submission #1174379
Source Code Expand
import java.util.ArrayList;
import java.util.Scanner;
import java.util.SplittableRandom;
public class Main {
static long startTime = System.currentTimeMillis();
static final int TL = 3990;
static final int[] DR = new int[]{1, 0, -1, 0, 0};
static final int[] DC = new int[]{0, 1, 0, -1, 0};
static final char[] DIR_CHARS = "DRUL-".toCharArray();
static Scanner sc = new Scanner(System.in);
static SplittableRandom rnd = new SplittableRandom(42);
static int H, W, K, T;
static int[][] carPos, origCarPos, convergePos;
static char[][] moves;
static int[] order;
static int time;
static int sumDist;
static int[][] used;
static int usedIdx;
public static void main(String[] args) {
H = sc.nextInt();
W = sc.nextInt();
K = sc.nextInt();
T = sc.nextInt();
carPos = new int[4][K];
origCarPos = new int[4][K];
convergePos = new int[4][K];
order = new int[K];
for (int i = 0; i < K; i++) {
for (int j = 0; j < 4; j++) {
origCarPos[j][i] = sc.nextInt() - 1;
}
order[i] = i;
}
moves = new char[T][K];
used = new int[H][W];
ArrayList<String> ans = new ArrayList<>();
double ansScore = 0;
long worstTime = 0;
for (int turn = 0; ; turn++) {
long beforeTime = System.currentTimeMillis() - startTime;
if (beforeTime + worstTime > TL) {
System.err.println("turn:" + turn);
break;
}
for (int i = 0; i < 4; i++) {
System.arraycopy(origCarPos[i], 0, carPos[i], 0, K);
}
sumDist = 0;
for (int i = 0; i < K; i++) {
sumDist += Math.abs(carPos[0][i] - carPos[2][i]) + Math.abs(carPos[1][i] - carPos[3][i]);
}
int bestTime = 0;
double bestScore = calcScore(sumDist, 0);
for (time = 1; time <= T; time++) {
boolean update = move();
if (!update) break;
double score = calcScore(sumDist, time);
if (score > bestScore) {
bestScore = score;
bestTime = time;
}
if (calcScore(0, time) < ansScore) {
System.err.println("time:" + time);
break;
}
}
System.err.println("bestScore:" + bestScore);
if (bestScore > ansScore) {
ansScore = bestScore;
ans.clear();
for (int i = 0; i < bestTime; i++) {
ans.add(String.valueOf(moves[i]));
}
}
worstTime = Math.max(worstTime, System.currentTimeMillis() - startTime - beforeTime);
}
System.out.println(ans.size());
for (String s : ans) {
System.out.println(s);
}
}
static boolean move() {
usedIdx++;
for (int i = 0; i < K; i++) {
int pos = rnd.nextInt(K - i) + i;
int tmp = order[i];
order[i] = order[pos];
order[pos] = tmp;
used[carPos[0][i]][carPos[1][i]] = usedIdx;
}
ArrayList<Integer> nearList = new ArrayList<>();
ArrayList<Integer> farList = new ArrayList<>();
int stayFactor;
if (sumDist < 100) {
stayFactor = 99;
} else if (sumDist < 200) {
stayFactor = 4;
} else if (sumDist < 300) {
stayFactor = 2;
} else if (sumDist < 500) {
stayFactor = 2;
} else if (sumDist < 1000) {
stayFactor = 1;
} else {
stayFactor = 0;
}
sumDist = 0;
boolean update = false;
for (int i = 0; i < K; i++) {
nearList.clear();
farList.clear();
int ci = order[i];
int dist = Math.abs(carPos[1][ci] - carPos[3][ci]) + Math.abs(carPos[0][ci] - carPos[2][ci]);
for (int j = 0; j < 4; j++) {
int nr = carPos[0][ci] + DR[j];
int nc = carPos[1][ci] + DC[j];
if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
if (used[nr][nc] == usedIdx) continue;
int nDist = Math.abs(nr - carPos[2][ci]) + Math.abs(nc - carPos[3][ci]);
if (dist > nDist) {
nearList.add(j);
} else {
farList.add(j);
}
}
int dir;
if (dist == 0 && stayFactor == 99) {
dir = 4;
} else if (nearList.size() == 1) {
dir = nearList.get(0);
--dist;
} else if (nearList.size() == 2) {
int nr0 = carPos[0][ci] + DR[nearList.get(0)];
int nc0 = carPos[1][ci] + DC[nearList.get(0)];
int distFromEdge0 = distFromEdge(nr0, nc0);
int nr1 = carPos[0][ci] + DR[nearList.get(1)];
int nc1 = carPos[1][ci] + DC[nearList.get(1)];
int distFromEdge1 = distFromEdge(nr1, nc1);
if (distFromEdge0 < distFromEdge1) {
nearList.add(nearList.get(0));
} else if (distFromEdge0 > distFromEdge1) {
nearList.add(nearList.get(1));
}
dir = nearList.get(rnd.nextInt(nearList.size()));
--dist;
} else if (!farList.isEmpty()) {
if (stayFactor == 0 && farList.size() >= 2) {
int nr0 = carPos[0][ci] + DR[farList.get(0)];
int nc0 = carPos[1][ci] + DC[farList.get(0)];
int distFromEdge0 = distFromEdge(nr0, nc0);
int nr1 = carPos[0][ci] + DR[farList.get(1)];
int nc1 = carPos[1][ci] + DC[farList.get(1)];
int distFromEdge1 = distFromEdge(nr1, nc1);
if (distFromEdge0 < distFromEdge1) {
farList.add(farList.get(0));
} else if (distFromEdge0 > distFromEdge1) {
farList.add(farList.get(1));
}
}
for (int j = 0; j < stayFactor; j++) {
farList.add(4);
}
dir = farList.get(rnd.nextInt(farList.size()));
if (dir != 4) dist++;
} else {
dir = 4;
}
moves[time - 1][ci] = DIR_CHARS[dir];
carPos[0][ci] += DR[dir];
carPos[1][ci] += DC[dir];
used[carPos[0][ci]][carPos[1][ci]] = usedIdx;
sumDist += dist;
if (dir != 4) update = true;
}
return update;
}
static int distFromEdge(int r, int c) {
return Math.min(Math.min(r, H - 1 - r), Math.min(c, W - 1 - c));
}
static double calcScore(int dist, int time) {
double distFactor = 20 + dist;
double timeFactor = 10 + 0.01 * time;
return 10_000_000.0 / (distFactor * timeFactor);
}
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
tomerun |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
800461 |
Code Size |
7414 Byte |
Status |
AC |
Exec Time |
3891 ms |
Memory |
60120 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 |
29326 / 50000 |
30322 / 50000 |
29121 / 50000 |
27825 / 50000 |
25044 / 50000 |
26667 / 50000 |
23497 / 50000 |
29482 / 50000 |
24202 / 50000 |
24962 / 50000 |
26897 / 50000 |
25240 / 50000 |
25051 / 50000 |
26169 / 50000 |
24571 / 50000 |
27825 / 50000 |
25988 / 50000 |
27145 / 50000 |
24814 / 50000 |
25721 / 50000 |
28043 / 50000 |
28297 / 50000 |
27732 / 50000 |
24438 / 50000 |
25760 / 50000 |
29586 / 50000 |
26414 / 50000 |
25563 / 50000 |
25155 / 50000 |
29604 / 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 |
3714 ms |
57060 KB |
subtask_01_02.txt |
AC |
3878 ms |
55436 KB |
subtask_01_03.txt |
AC |
3712 ms |
55296 KB |
subtask_01_04.txt |
AC |
3661 ms |
54000 KB |
subtask_01_05.txt |
AC |
3723 ms |
58112 KB |
subtask_01_06.txt |
AC |
3780 ms |
55472 KB |
subtask_01_07.txt |
AC |
3765 ms |
54656 KB |
subtask_01_08.txt |
AC |
3758 ms |
57388 KB |
subtask_01_09.txt |
AC |
3769 ms |
55956 KB |
subtask_01_10.txt |
AC |
3820 ms |
57796 KB |
subtask_01_11.txt |
AC |
3677 ms |
55332 KB |
subtask_01_12.txt |
AC |
3428 ms |
54780 KB |
subtask_01_13.txt |
AC |
3538 ms |
55536 KB |
subtask_01_14.txt |
AC |
3821 ms |
57332 KB |
subtask_01_15.txt |
AC |
3672 ms |
53312 KB |
subtask_01_16.txt |
AC |
3886 ms |
55884 KB |
subtask_01_17.txt |
AC |
3813 ms |
53200 KB |
subtask_01_18.txt |
AC |
3826 ms |
54904 KB |
subtask_01_19.txt |
AC |
3793 ms |
57436 KB |
subtask_01_20.txt |
AC |
3777 ms |
58364 KB |
subtask_01_21.txt |
AC |
3799 ms |
57824 KB |
subtask_01_22.txt |
AC |
3891 ms |
52980 KB |
subtask_01_23.txt |
AC |
3828 ms |
55840 KB |
subtask_01_24.txt |
AC |
3861 ms |
57952 KB |
subtask_01_25.txt |
AC |
3757 ms |
57684 KB |
subtask_01_26.txt |
AC |
3745 ms |
60120 KB |
subtask_01_27.txt |
AC |
3849 ms |
57560 KB |
subtask_01_28.txt |
AC |
3792 ms |
56756 KB |
subtask_01_29.txt |
AC |
3853 ms |
55532 KB |
subtask_01_30.txt |
AC |
3865 ms |
55832 KB |