結果
問題 | No.1508 Avoid being hit |
ユーザー | 遭難者 |
提出日時 | 2021-04-02 18:30:14 |
言語 | Java (openjdk 23) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 18,381 bytes |
コンパイル時間 | 3,216 ms |
コンパイル使用メモリ | 95,724 KB |
実行使用メモリ | 93,144 KB |
最終ジャッジ日時 | 2024-09-25 02:25:13 |
合計ジャッジ時間 | 18,188 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 66 ms
50,728 KB |
testcase_02 | AC | 72 ms
50,664 KB |
testcase_03 | AC | 63 ms
50,548 KB |
testcase_04 | AC | 65 ms
50,788 KB |
testcase_05 | AC | 70 ms
51,048 KB |
testcase_06 | AC | 72 ms
51,000 KB |
testcase_07 | AC | 64 ms
50,460 KB |
testcase_08 | AC | 63 ms
50,872 KB |
testcase_09 | AC | 64 ms
50,648 KB |
testcase_10 | AC | 69 ms
51,028 KB |
testcase_11 | AC | 65 ms
50,788 KB |
testcase_12 | AC | 63 ms
50,452 KB |
testcase_13 | AC | 63 ms
50,804 KB |
testcase_14 | AC | 62 ms
50,704 KB |
testcase_15 | AC | 68 ms
51,048 KB |
testcase_16 | AC | 271 ms
73,640 KB |
testcase_17 | AC | 218 ms
65,484 KB |
testcase_18 | AC | 225 ms
65,404 KB |
testcase_19 | AC | 265 ms
69,452 KB |
testcase_20 | AC | 375 ms
79,436 KB |
testcase_21 | AC | 270 ms
73,316 KB |
testcase_22 | AC | 295 ms
76,352 KB |
testcase_23 | AC | 308 ms
79,208 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 171 ms
57,956 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 461 ms
84,428 KB |
testcase_35 | AC | 142 ms
55,476 KB |
testcase_36 | AC | 288 ms
67,472 KB |
testcase_37 | AC | 203 ms
62,568 KB |
testcase_38 | AC | 452 ms
83,268 KB |
testcase_39 | AC | 269 ms
66,928 KB |
testcase_40 | AC | 503 ms
93,144 KB |
testcase_41 | AC | 348 ms
62,556 KB |
testcase_42 | AC | 497 ms
83,736 KB |
testcase_43 | AC | 622 ms
88,256 KB |
testcase_44 | AC | 62 ms
37,536 KB |
testcase_45 | AC | 67 ms
38,292 KB |
ソースコード
import java.util.*;import java.io.*;public class Main {public static void solve(ContestScanner sc, ContestPrinter ou) {int n = sc.nextInt();int q = sc.nextInt();var a = sc.nextIntArray(q, i -> i - 1);var b = sc.nextIntArray(q, i -> i - 1);for (int i = 0; i < q; i++) {if (a[i] > b[i]) {int tmp = a[i];a[i] = b[i];b[i] = tmp;}}if (q == 1) {for (int i = 0; i < n; i++) {if (a[0] != i && b[0] != i) {ou.println("YES");ou.println(i);ou.println(i);return;}}ou.println("NO");return;}var g = new ArrayList<ArrayList<Point>>();var kk = new ArrayList<ArrayList<Point>>();var k = new int[q];for (int i = 0; i <= q; i++) {g.add(new ArrayList<>());kk.add(new ArrayList<>());}g.get(0).add(new Point(0, n - 1));kk.get(0).add(new Point(0, n - 1));for (int i = 0; i < q; i++) {for (Point p : g.get(i)) {p.x--;p.y++;p.x = max(0, p.x);p.y = min(n - 1, p.y);if (p.x <= a[i] && a[i] <= p.y) {g.get(i + 1).add(new Point(p.x, a[i] - 1));p.x = a[i] + 1;}if (p.x <= b[i] && b[i] <= p.y) {g.get(i + 1).add(new Point(p.x, b[i] - 1));p.x = b[i] + 1;}g.get(i + 1).add(new Point(p.x, p.y));}if (!g.get(i).isEmpty()) {try {var gg = new ArrayList<Point>();Point r = g.get(i + 1).remove(0);while (r.x > r.y) {r = g.get(i + 1).remove(0);}for (Point p : g.get(i + 1)) {if (p.x <= p.y) {if (r.y + 1 >= p.x) {r.x = min(r.x, p.x);r.y = max(r.y, p.y);r = p;} else {gg.add(new Point(r.x, r.y));r = p;}}}gg.add(r);g.get(i + 1).clear();for (Point p : gg) {g.get(i + 1).add(new Point(p.x, p.y));kk.get(i + 1).add(new Point(p.x, p.y));}} catch (IndexOutOfBoundsException $) {}}}if (g.get(q).isEmpty())ou.println("NO");else {k[q - 1] = g.get(q).remove(0).x;for (int i = q - 2; i >= 0; i--) {boolean aa, bb;aa = bb = false;for (var p : kk.get(i + 1)) {if (p.x <= k[i + 1] - 1 && k[i + 1] - 1 <= p.y)aa = true;if (p.x <= k[i + 1] && k[i + 1] <= p.y)bb = true;}if (k[i + 1] - 1 < 0)aa = false;if (aa)k[i] = k[i + 1] - 1;else if (bb)k[i] = k[i + 1];elsek[i] = k[i + 1] + 1;}ou.println("YES");ou.println(k[0] + 1);ou.printlnArray(k, i -> i + 1);}}public static void main(String[] args) {var sc = new ContestScanner();var ou = new ContestPrinter();solve(sc, ou);ou.flush();ou.close();}public static int max(int s, int... a) {for (int i : a)if (s < i)s = i;return s;}public static long max(long s, long... a) {for (long i : a)if (s < i)s = i;return s;}public static int min(int s, int... a) {for (int i : a)if (s > i)s = i;return s;}public static long min(long s, long... a) {for (long i : a)if (s > i)s = i;return s;}static class Point {int x;int y;Point(int x, int y) {this.x = x;this.y = y;}int compareTo(Point p) {long c = this.x - p.x;if (c < 0)return -1;if (c > 0)return 1;return 0;}boolean equals(Point p) {return this.x == p.x && this.y == p.y;}String r() {return this.x + " " + this.y;}}static class Point2 {long x;int y;Point2(long x, int y) {this.x = x;this.y = y;}int compareTo(Point2 p) {long c = this.x - p.x;if (c < 0)return -1;if (c > 0)return 1;return 0;}boolean equals(Point2 p) {return this.x == p.x && this.y == p.y;}}}class ContestScanner {private final InputStream in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;public ContestScanner(InputStream in) {this.in = in;}public ContestScanner() {this(System.in);}private boolean hasNextByte() {if (ptr < buflen)return true;ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0)return false;return true;}private int readByte() {return hasNextByte() ? buffer[ptr++] : -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(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 void nextThrow(int n) {for (int i = 0; i < n; i++)this.next();}public void nextThrow() {this.nextThrow(1);}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;elsethrow 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 double nextDouble() {return Double.parseDouble(next());}public boolean[] nextBoolean(char True) {String s = this.next();int n = s.length();boolean[] array = new boolean[n];for (int i = 0; i < n; i++)array[i] = s.charAt(i) == True;return array;}public long[] nextLongArray(int length) {long[] array = new long[length];for (int i = 0; i < length; i++)array[i] = this.nextLong();return array;}public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map) {long[] array = new long[length];for (int i = 0; i < length; i++)array[i] = map.applyAsLong(this.nextLong());return array;}public int[] nextIntArray(int length) {int[] array = new int[length];for (int i = 0; i < length; i++)array[i] = this.nextInt();return array;}public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map) {int[] array = new int[length];for (int i = 0; i < length; i++)array[i] = map.applyAsInt(this.nextInt());return array;}public int[] nextIntArray(int length, int[] array) {int n = length + array.length;int[] a = new int[n];for (int i = 0; i < length; i++)a[i] = this.nextInt();for (int i = length; i < n; i++)a[i] = array[i - length];return a;}public Integer[] nextIntegerArray(int length, java.util.function.IntUnaryOperator map) {Integer[] array = new Integer[length];for (int i = 0; i < length; i++)array[i] = map.applyAsInt(this.nextInt());return array;}public Integer[] nextIntegerArray(int length) {Integer[] array = new Integer[length];for (int i = 0; i < length; i++)array[i] = this.nextInt();return array;}public double[] nextDoubleArray(int length) {double[] array = new double[length];for (int i = 0; i < length; i++)array[i] = this.nextDouble();return array;}public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map) {double[] array = new double[length];for (int i = 0; i < length; i++)array[i] = map.applyAsDouble(this.nextDouble());return array;}public String[] nextArray(int length) {String[] array = new String[length];for (int i = 0; i < length; i++)array[i] = this.next();return array;}public long[][] nextLongMatrix(int height, int width) {long[][] mat = new long[height][width];for (int h = 0; h < height; h++)for (int w = 0; w < width; w++)mat[h][w] = this.nextLong();return mat;}public int[][] nextIntMatrix(int height, int width) {int[][] mat = new int[height][width];for (int h = 0; h < height; h++)for (int w = 0; w < width; w++)mat[h][w] = this.nextInt();return mat;}public double[][] nextDoubleMatrix(int height, int width) {double[][] mat = new double[height][width];for (int h = 0; h < height; h++)for (int w = 0; w < width; w++)mat[h][w] = this.nextDouble();return mat;}public boolean[][] nextBooleanMatrix(int height, int width, char True) {boolean[][] mat = new boolean[height][width];for (int h = 0; h < height; h++) {String s = this.next();for (int w = 0; w < width; w++)mat[h][w] = s.charAt(w) == True;}return mat;}public char[][] nextCharMatrix(int height, int width) {char[][] mat = new char[height][width];for (int h = 0; h < height; h++) {String s = this.next();for (int w = 0; w < width; w++)mat[h][w] = s.charAt(w);}return mat;}public char[][] nextCharMatrix(int height, int width, int h, int w, char c) {char[][] mat = new char[height + 2 * h][width + 2 * w];for (int i = 0; i < height; i++) {String s = this.next();for (int j = 0; j < width; j++)mat[i + h][j + w] = s.charAt(j);}for (int i = 0; i < h; i++)for (int j = 0; j < 2 * w + width; j++)mat[i][j] = c;for (int i = h + height; i < 2 * h + height; i++)for (int j = 0; j < 2 * w + width; j++)mat[i][j] = c;for (int i = h; i < h + height; i++) {for (int j = 0; j < w; j++)mat[i][j] = c;for (int j = w + width; j < 2 * w + width; j++)mat[i][j] = c;}return mat;}public boolean[][] nextBooleanMatrix(int height, int width, int h, int w, char c) {boolean[][] mat = new boolean[height + 2 * h][width + 2 * w];for (int i = 0; i < height; i++) {String s = this.next();for (int j = 0; j < width; j++)mat[i + h][j + w] = s.charAt(j) == c;}return mat;}}class ContestPrinter extends PrintWriter {public ContestPrinter(PrintStream stream) {super(stream);}public ContestPrinter() {super(System.out);}private static String dtos(double x, int n) {StringBuilder sb = new StringBuilder();if (x < 0) {sb.append('-');x = -x;}x += Math.pow(10, -n) / 2;sb.append((long) x);sb.append(".");x -= (long) x;for (int i = 0; i < n; i++) {x *= 10;sb.append((int) x);x -= (int) x;}return sb.toString();}@Overridepublic void print(float f) {super.print(dtos(f, 20));}@Overridepublic void println(float f) {super.println(dtos(f, 20));}@Overridepublic void print(double d) {super.print(dtos(d, 20));}@Overridepublic void println(double d) {super.println(dtos(d, 20));}public void printlnArray(String[] array) {for (String i : array)super.println(i);}public void printArray(int[] array, String separator) {int n = array.length - 1;for (int i = 0; i < n; i++) {super.print(array[i]);super.print(separator);}super.println(array[n]);}public void printArray(int[] array) {this.printArray(array, " ");}public void printlnArray(int[] array) {for (int i : array)super.println(i);}public void printArray(int[] array, String separator, java.util.function.IntUnaryOperator map) {int n = array.length - 1;for (int i = 0; i < n; i++) {super.print(map.applyAsInt(array[i]));super.print(separator);}super.println(map.applyAsInt(array[n]));}public void printlnArray(int[] array, java.util.function.IntUnaryOperator map) {for (int i : array)super.println(map.applyAsInt(i));}public void printlnArray(long[] array, java.util.function.LongUnaryOperator map) {for (long i : array)super.println(map.applyAsLong(i));}public void printArray(int[] array, java.util.function.IntUnaryOperator map) {this.printArray(array, " ", map);}public void printArray(long[] array, String separator) {int n = array.length - 1;for (int i = 0; i < n; i++) {super.print(array[i]);super.print(separator);}super.println(array[n]);}public void printArray(long[] array) {this.printArray(array, " ");}public void printlnArray(long[] array) {for (long i : array)super.println(i);}public void printArray(boolean[] array, String a, String b) {int n = array.length - 1;for (int i = 0; i < n; i++)super.print((array[i] ? a : b) + " ");super.println(array[n] ? a : b);}public void printArray(boolean[] array) {this.printArray(array, "Y", "N");}public void printArray(long[] array, String separator, java.util.function.LongUnaryOperator map) {int n = array.length - 1;for (int i = 0; i < n; i++) {super.print(map.applyAsLong(array[i]));super.print(separator);}super.println(map.applyAsLong(array[n]));}public void printArray(long[] array, java.util.function.LongUnaryOperator map) {this.printArray(array, " ", map);}public void printArray(ArrayList<?> array) {this.printArray(array, " ");}public void printArray(ArrayList<?> array, String separator) {int n = array.size() - 1;for (int i = 0; i < n; i++) {super.print(array.get(i).toString());super.print(separator);}super.println(array.get(n).toString());}public void printlnArray(ArrayList<?> array) {int n = array.size();for (int i = 0; i < n; i++)super.println(array.get(i).toString());}public void printArray(int[][] array) {int n = array.length;if (n == 0)return;int m = array[0].length - 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)super.print(array[i][j] + " ");super.println(array[i][m]);}}public void printArray(long[][] array) {int n = array.length;if (n == 0)return;int m = array[0].length - 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)super.print(array[i][j] + " ");super.println(array[i][m]);}}// debugpublic void printArray(boolean[][] array) {int n = array.length;if (n == 0)return;int m = array[0].length - 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)super.print(array[i][j] ? "○ " : "× ");super.println(array[i][m] ? "○" : "×");}}}