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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 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
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