Submission #1175386

---

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) {
					if (phase == 0) {
						freeze = 0;
						phase = 1;
					}
				}
				if (freeze > FREEZE2) {
					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

Judge Result