結果
| 問題 |
No.1307 Rotate and Accumulate
|
| コンテスト | |
| ユーザー |
 suisen
|
| 提出日時 | 2020-12-05 15:25:30 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 28,662 bytes |
| コンパイル時間 | 3,541 ms |
| コンパイル使用メモリ | 101,032 KB |
| 実行使用メモリ | 37,308 KB |
| 最終ジャッジ日時 | 2024-09-15 17:45:07 |
| 合計ジャッジ時間 | 5,811 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 19 |
ソースコード
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
public class Main {
public static void main(String[] args) throws Exception {
ExtendedScanner sc = new ExtendedScanner();
FastPrintStream pw = new FastPrintStream();
solve(sc, pw);
sc.close();
pw.flush();
pw.close();
}
public static void solve(ExtendedScanner sc, FastPrintStream pw) {
final int M = 1000;
final int N = sc.nextInt();
final int Q = sc.nextInt();
final int[] _A = sc.ints(N);
final int[] P = IndexSort.sort(_A);
final int[] IP = new int[N];
for (int i = 0; i < N; i++) {
IP[P[i]] = i;
}
IntRadixSort.sort(_A);
final int[] A = new int[N << 1];
System.arraycopy(_A, 0, A, 0, N);
System.arraycopy(_A, 0, A, N, N);
final int[] C = new int[N];
for (int r : sc.ints(Q)) {
C[r]++;
}
final int[] Ra = new int[M + 1];
for (int i = 1; i < N; i++) {
if (A[i] != A[i - 1]) {
Ra[A[i - 1]] = i;
}
}
Ra[A[N - 1]] = N;
final int[] R = new int[N << 1];
for (int i = 0; i < N; i++) {
R[i] = Ra[A[i]];
R[i + N] = R[i] + N;
}
int[] imos = new int[N << 1 | 1];
for (int i = 0; i < N; i++) {
if (C[i] == 0) continue;
int l = i, r = Math.min(R[i], i + N);
while (l < i + N) {
int val = A[l];
imos[l - i] += val * C[i];
imos[r - i] -= val * C[i];
l = r;
r = Math.min(R[l], i + N);
}
}
for (int i = 1; i <= N << 1; i++) {
imos[i] += imos[i - 1];
}
int[] ans = new int[N];
for (int i = 0; i < N; i++) {
ans[i] = imos[i] + imos[i + N];
}
IntArrays.permute(IP, ans);
pw.println(IntArrays.join(ans, " "));
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastScanner implements AutoCloseable {
private final ByteBuffer tokenBuf = new ByteBuffer();
private final java.io.InputStream in;
private final byte[] rawBuf = new byte[1 << 14];
private int ptr = 0;
private int buflen = 0;
public FastScanner(java.io.InputStream in) {
this.in = in;
}
public FastScanner() {
this(new java.io.FileInputStream(java.io.FileDescriptor.in));
}
private final int readByte() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
throw new java.io.EOFException();
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int readByteUnsafe() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
return -1;
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int skipUnprintableChars() {
int b = readByte();
while (b <= 32 || b >= 127) b = readByte();
return b;
}
private final void loadToken() {
tokenBuf.clear();
for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
tokenBuf.append(b);
}
}
public final boolean hasNext() {
for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
if (b == -1) return false;
}
--ptr;
return true;
}
public final String next() {
loadToken();
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final String nextLine() {
tokenBuf.clear();
for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
if (b == -1) break;
tokenBuf.append(b);
}
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final char nextChar() {
return (char) skipUnprintableChars();
}
public final char[] nextChars() {
loadToken();
return tokenBuf.toCharArray();
}
public final long nextLong() {
long n = 0;
boolean isNegative = false;
int b = skipUnprintableChars();
if (b == '-') {
isNegative = true;
b = readByteUnsafe();
}
if (b < '0' || '9' < b) throw new NumberFormatException();
while ('0' <= b && b <= '9') {
// -9223372036854775808 - 9223372036854775807
if (n >= 922337203685477580l) {
if (n > 922337203685477580l) {
throw new ArithmeticException("long overflow");
}
if (isNegative) {
if (b >= '9') {
throw new ArithmeticException("long overflow");
}
n = -n - (b + '0');
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
} else {
if (b >= '8') {
throw new ArithmeticException("long overflow");
}
n = n * 10 + b - '0';
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
}
}
n = n * 10 + b - '0';
b = readByteUnsafe();
}
if (b <= 32 || b >= 127) return isNegative ? -n : n;
throw new NumberFormatException();
}
public final int nextInt() {
long value = nextLong();
if ((int) value != value) {
throw new ArithmeticException("int overflow");
}
return (int) value;
}
public final double nextDouble() {
return Double.parseDouble(next());
}
public final void close() {
try {
in.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static final class ByteBuffer {
private static final int DEFAULT_BUF_SIZE = 1 << 12;
private byte[] buf;
private int ptr = 0;
private ByteBuffer(int capacity) {
this.buf = new byte[capacity];
}
private ByteBuffer() {
this(DEFAULT_BUF_SIZE);
}
private ByteBuffer append(int b) {
if (ptr == buf.length) {
int newLength = buf.length << 1;
byte[] newBuf = new byte[newLength];
System.arraycopy(buf, 0, newBuf, 0, buf.length);
buf = newBuf;
}
buf[ptr++] = (byte) b;
return this;
}
private char[] toCharArray() {
char[] chs = new char[ptr];
for (int i = 0; i < ptr; i++) {
chs[i] = (char) buf[i];
}
return chs;
}
private byte[] getRawBuf() {
return buf;
}
private int size() {
return ptr;
}
private void clear() {
ptr = 0;
}
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class ExtendedScanner extends FastScanner {
public ExtendedScanner() {super();}
public ExtendedScanner(InputStream in) {super(in);}
public int[] ints(final int n) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> nextInt());
return a;
}
public int[] ints(final int n, final IntUnaryOperator f) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
return a;
}
public int[][] ints(final int n, final int m) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m));
return a;
}
public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m, f));
return a;
}
public long[] longs(final int n) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> nextLong());
return a;
}
public long[] longs(final int n, final LongUnaryOperator f) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
return a;
}
public long[][] longs(final int n, final int m) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m));
return a;
}
public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m, f));
return a;
}
public char[][] charArrays(final int n) {
final char[][] c = new char[n][];
Arrays.setAll(c, $ -> nextChars());
return c;
}
public double[] doubles(final int n) {
final double[] a = new double[n];
Arrays.setAll(a, $ -> nextDouble());
return a;
}
public double[][] doubles(final int n, final int m) {
final double[][] a = new double[n][];
Arrays.setAll(a, $ -> doubles(m));
return a;
}
public String[] strings(final int n) {
final String[] s = new String[n];
Arrays.setAll(s, $ -> next());
return s;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class IntArrays {
private IntArrays(){}
public static void swap(int[] a, int u, int v) {
int tmp = a[u]; a[u] = a[v]; a[v] = tmp;
}
public static void reverse(int[] a, int l, int r) {
while (r - l > 1) swap(a, l++, --r);
}
public static void reverse(int[] a) {
reverse(a, 0, a.length);
}
public static int sum(int[] a) {
int sum = 0;
for (int e : a) sum += e;
return sum;
}
public static int max(int[] a) {
int max = a[0];
for (int e : a) max = Math.max(max, e);
return max;
}
public static int min(int[] a) {
int min = a[0];
for (int e : a) min = Math.min(min, e);
return min;
}
public static int argmax(int[] a) {
int max = a[0], argmax = 0;
for (int i = 0; i < a.length; i++) if (max < a[i]) max = a[argmax = i];
return argmax;
}
public static int argmin(int[] a) {
int min = a[0], argmin = 0;
for (int i = 0; i < a.length; i++) if (min > a[i]) min = a[argmin = i];
return argmin;
}
public static int find(int[] a, int v) {
for (int i = 0; i < a.length; i++) if (a[i] == v) return i;
return -1;
}
public static void permute(int[] p, int[] a) {
int n = p.length;
boolean[] settled = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = i; !settled[j]; j = p[j]) {
settled[j] = true;
if (p[j] == i) break;
swap(a, j, p[j]);
}
}
}
public static void permute2(int[] p, int[] a, int[] b) {
int n = p.length;
boolean[] settled = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = i; !settled[j]; j = p[j]) {
settled[j] = true;
if (p[j] == i) break;
swap(a, j, p[j]); swap(b, j, p[j]);
}
}
}
public static void permute3(int[] p, int[] a, int[] b, int[] c) {
int n = p.length;
boolean[] settled = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = i; !settled[j]; j = p[j]) {
settled[j] = true;
if (p[j] == i) break;
swap(a, j, p[j]); swap(b, j, p[j]); swap(c, j, p[j]);
}
}
}
public static void permuteN(int[] p, int[]... as) {
int n = p.length;
boolean[] settled = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = i; !settled[j]; j = p[j]) {
settled[j] = true;
if (p[j] == i) break;
for (int[] a : as) swap(a, j, p[j]);
}
}
}
public static int lowerBound(int[] sorted, int key) {
int n = sorted.length;
int l = -1, r = n;
while (r - l > 1) {
int m = (l + r) >> 1;
if (sorted[m] < key) l = m;
else r = m;
}
return r;
}
public static int upperBound(int[] sorted, int key) {
int n = sorted.length;
int l = -1, r = n;
while (r - l > 1) {
int m = (l + r) >> 1;
if (sorted[m] <= key) l = m;
else r = m;
}
return r;
}
public static int countOfRange(int[] sorted, int from, int to) {
return lowerBound(sorted, to) - lowerBound(sorted, from);
}
public static String join(int[] a, String sep) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < a.length; i++) {
sb.append(a[i]);
if (i < a.length - 1) sb.append(sep);
}
return sb.toString();
}
public static String join(int[] a, char sep) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < a.length; i++) {
sb.append(a[i]);
if (i < a.length - 1) sb.append(sep);
}
return sb.toString();
}
}
final class IntMergeSortUsingComparator {
private static int INSERTION_SORT_THRESHOLD = 60;
public static void sort(int[] a, IntComparator comparator) {
sort(a, 0, a.length, comparator);
}
public static void sortDesc(int[] a, IntComparator comparator) {
sortDesc(a, 0, a.length, comparator);
}
public static void sort(int[] a, int l, int r, IntComparator comparator) {
for (int i = l;;) {
int j = i + INSERTION_SORT_THRESHOLD;
if (j < r) {
IntInsertionSortUsingComparator.sort(a, i, i = j, comparator);
} else {
IntInsertionSortUsingComparator.sort(a, i, r, comparator);
break;
}
}
final int w = r - l;
int[] work = new int[w];
for (int size = INSERTION_SORT_THRESHOLD; size <= w; size <<= 1) {
int size2 = size << 1;
int blmax = r - size;
for (int bl = l; bl < blmax; bl += size2) {
int bm = bl + size;
int br = Math.min(bl + size2, r);
System.arraycopy(a, bl, work, 0, size);
int ai = bl, li = 0, ri = bm;
while (true) {
if (ri == br) {
System.arraycopy(work, li, a, ai, size - li);
break;
}
if (comparator.gt(work[li], a[ri])) {
a[ai++] = a[ri++];
} else {
a[ai++] = work[li++];
if (li == size) break;
}
}
}
}
}
public static void sortDesc(int[] a, int from, int to, IntComparator comparator) {
sort(a, from, to, comparator);
int l = from, r = to - 1;
while (l < r) {
int tmp = a[l]; a[l] = a[r]; a[r] = tmp;
l++; r--;
}
}
}
final class IndexSort {
private static int[] indecies(int n) {
int[] ret = new int[n];
java.util.Arrays.setAll(ret, i -> i);
return ret;
}
public static int[] sort(int[] a) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> a[i] - a[j]);
return index;
}
public static int[] sortDesc(int[] a) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> a[j] - a[i]);
return index;
}
public static int[] sort(long[] a) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> Long.compare(a[i], a[j]));
return index;
}
public static int[] sortDesc(long[] a) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> Long.compare(a[j], a[i]));
return index;
}
public static <T extends Comparable<T>> int[] sort(T[] a) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> a[i].compareTo(a[j]));
return index;
}
public static <T> int[] sort(T[] a, Comparator<T> comparator) {
int[] index = indecies(a.length);
IntMergeSortUsingComparator.sort(index, (i, j) -> comparator.compare(a[i], a[j]));
return index;
}
}
@FunctionalInterface
interface IntComparator {
public int compare(int i, int j);
public default boolean eq(final int i, final int j) {return compare(i, j) == 0;}
public default boolean ne(final int i, final int j) {return compare(i, j) != 0;}
public default boolean gt(final int i, final int j) {return compare(i, j) > 0;}
public default boolean ge(final int i, final int j) {return compare(i, j) >= 0;}
public default boolean lt(final int i, final int j) {return compare(i, j) < 0;}
public default boolean le(final int i, final int j) {return compare(i, j) <= 0;}
}
class IntRadixSort {
private static final int INT_INSERTION_SORT_THRESHOLD = 120;
public static void sort(int[] a) {
sort(a, 0, a.length);
}
public static void sortDesc(int[] a) {
sortDesc(a, 0, a.length);
}
public static void sort(int[] a, int fr, int to) {
if (to - fr <= INT_INSERTION_SORT_THRESHOLD) {
IntInsertionSort.sort(a, fr, to);
return;
}
int[] c0 = new int[0x101];
int[] c1 = new int[0x101];
int[] c2 = new int[0x101];
int[] c3 = new int[0x101];
c0[0] = c1[0] = c2[0] = c3[0] = fr;
for (int i = fr; i < to; i++) {
int v = a[i];
c0[(v & 0xff) + 1]++;
c1[(v >>> 8 & 0xff) + 1]++;
c2[(v >>> 16 & 0xff) + 1]++;
c3[(v >>> 24 ^ 0x80) + 1]++;
}
for (int i = 0; i < 0x100; i++) {
c0[i + 1] += c0[i];
c1[i + 1] += c1[i];
c2[i + 1] += c2[i];
c3[i + 1] += c3[i];
}
int[] b = new int[a.length];
for (int i = fr; i < to; i++) {int v = a[i]; b[c0[v & 0xff]++] = v;}
for (int i = fr; i < to; i++) {int v = b[i]; a[c1[v >>> 8 & 0xff]++] = v;}
for (int i = fr; i < to; i++) {int v = a[i]; b[c2[v >>> 16 & 0xff]++] = v;}
for (int i = fr; i < to; i++) {int v = b[i]; a[c3[v >>> 24 ^ 0x80]++] = v;}
}
public static void sortDesc(int[] a, int fr, int to) {
sort(a, fr, to);
int l = fr, r = to - 1;
while (l < r) {int tmp = a[l]; a[l] = a[r]; a[r] = tmp; l++; r--;}
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastPrintStream implements AutoCloseable {
private static final int INT_MAX_LEN = 11;
private static final int LONG_MAX_LEN = 20;
private int precision = 9;
private static final int BUF_SIZE = 1 << 14;
private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
private final byte[] buf = new byte[BUF_SIZE];
private int ptr = 0;
private final java.lang.reflect.Field strField;
private final java.nio.charset.CharsetEncoder encoder;
private final java.io.OutputStream out;
public FastPrintStream(java.io.OutputStream out) {
this.out = out;
java.lang.reflect.Field f;
try {
f = java.lang.String.class.getDeclaredField("value");
f.setAccessible(true);
} catch (NoSuchFieldException | SecurityException e) {
f = null;
}
this.strField = f;
this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();
}
public FastPrintStream(java.io.File file) throws java.io.IOException {
this(new java.io.FileOutputStream(file));
}
public FastPrintStream(java.lang.String filename) throws java.io.IOException {
this(new java.io.File(filename));
}
public FastPrintStream() {
this(new java.io.FileOutputStream(java.io.FileDescriptor.out));
}
public FastPrintStream println() {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) '\n';
return this;
}
public FastPrintStream println(java.lang.Object o) {
return print(o).println();
}
public FastPrintStream println(java.lang.String s) {
return print(s).println();
}
public FastPrintStream println(char[] s) {
return print(s).println();
}
public FastPrintStream println(char c) {
return print(c).println();
}
public FastPrintStream println(int x) {
return print(x).println();
}
public FastPrintStream println(long x) {
return print(x).println();
}
public FastPrintStream println(double d, int precision) {
return print(d, precision).println();
}
public FastPrintStream println(double d) {
return print(d).println();
}
private FastPrintStream print(byte[] bytes) {
int n = bytes.length;
if (ptr + n > BUF_SIZE) {
internalFlush();
try {
out.write(bytes);
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
} else {
System.arraycopy(bytes, 0, buf, ptr, n);
ptr += n;
}
return this;
}
public FastPrintStream print(java.lang.Object o) {
return print(o.toString());
}
public FastPrintStream print(java.lang.String s) {
if (strField == null) {
return print(s.getBytes());
} else {
try {
Object value = strField.get(s);
if (value instanceof byte[]) {
return print((byte[]) value);
} else {
return print((char[]) value);
}
} catch (IllegalAccessException e) {
return print(s.getBytes());
}
}
}
public FastPrintStream print(char[] s) {
try {
return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());
} catch (java.nio.charset.CharacterCodingException e) {
byte[] bytes = new byte[s.length];
for (int i = 0; i < s.length; i++) {
bytes[i] = (byte) s[i];
}
return print(bytes);
}
}
public FastPrintStream print(char c) {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) c;
return this;
}
public FastPrintStream print(int x) {
if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
if (-10 < x && x < 10) {
if (x < 0) {
buf[ptr++] = '-';
x = -x;
}
buf[ptr++] = (byte) ('0' + x);
return this;
}
int d;
if (x < 0) {
if (x == Integer.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(long x) {
if ((int) x == x) return print((int) x);
if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
int d;
if (x < 0) {
if (x == Long.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(double d, int precision) {
if (d < 0) {
print('-');
d = -d;
}
d += Math.pow(10, -precision) / 2;
print((long) d).print('.');
d -= (long) d;
for(int i = 0; i < precision; i++){
d *= 10;
print((int) d);
d -= (int) d;
}
return this;
}
public FastPrintStream print(double d) {
return print(d, precision);
}
public void setPrecision(int precision) {
this.precision = precision;
}
private void internalFlush() {
try {
out.write(buf, 0, ptr);
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void flush() {
try {
out.write(buf, 0, ptr);
out.flush();
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void close() {
try {
out.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static int len(int x) {
return
x >= 1000000000 ? 10 :
x >= 100000000 ? 9 :
x >= 10000000 ? 8 :
x >= 1000000 ? 7 :
x >= 100000 ? 6 :
x >= 10000 ? 5 :
x >= 1000 ? 4 :
x >= 100 ? 3 :
x >= 10 ? 2 : 1;
}
private static int len(long x) {
return
x >= 1000000000000000000l ? 19 :
x >= 100000000000000000l ? 18 :
x >= 10000000000000000l ? 17 :
x >= 1000000000000000l ? 16 :
x >= 100000000000000l ? 15 :
x >= 10000000000000l ? 14 :
x >= 1000000000000l ? 13 :
x >= 100000000000l ? 12 :
x >= 10000000000l ? 11 : 10;
}
}
final class IntInsertionSortUsingComparator {
static void sort(int[] a, int from, int to, IntComparator comparator) {
for (int i = from + 1; i < to; i++) {
int tmp = a[i];
if (comparator.gt(a[i - 1], tmp)) {
int j = i;
do {a[j] = a[--j];} while (j > from && comparator.gt(a[j - 1], tmp));
a[j] = tmp;
}
}
}
}
class IntInsertionSort {
static void sort(int[] a) {
sort(a, 0, a.length);
}
static void sort(int[] a, int from, int to) {
for (int i = from + 1; i < to; i++) {
int tmp = a[i];
if (a[i - 1] > tmp) {
int j = i;
do {a[j] = a[--j];} while (j > from && a[j - 1] > tmp);
a[j] = tmp;
}
}
}
}