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
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 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