Codeforces Round #377 (Div. 2) E. Sockets
問題
N 台のパソコンがあり、パソコン i の消費電力は Pi です。ソケットが M 個あり、ソケット j の供給電力は Sj です、消費電力と供給電力が等しいとき、パソコンをソケットに接続できます。1 つのソケットには 1 台のパソコンしか接続できません。アダプタを 1 個使うと、ソケットの供給電力を (Sj+1)/2 にします。できるだけ多くパソコンを繋いだ時のパソコンの台数とアダプタの最小値を求めてください。
解法
消費電力の大きいパソコンから見てソケットとペアを作り、使われなかったソケットはアダプタを追加していきます。制約が大きいので、高速化の工夫として、3つの変数を1つにすると良いです。他に、sort の代わりに radixsort を使う、ヒープを自前で実装する、などの工夫があります。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class E { private static class Task { void solve(FastScanner in, PrintWriter out) throws Exception { long start = System.currentTimeMillis(); int N = in.nextInt(); int M = in.nextInt(); int[] P = in.nextIntArray(N); int[] S = in.nextIntArray(M); int[][] powers = new int[N][2]; for (int i = 0; i < N; i++) { powers[i][0] = P[i]; powers[i][1] = i; } Arrays.sort(powers, (o1, o2) -> -(o1[0] - o2[0])); System.err.println(System.currentTimeMillis() - start); long[] sockets = new long[M * 31]; long bit32 = 1L << 32; long bit18 = 1L << 18; int pos = 0; for (int id = 0; id < M; id++) { long s = S[id]; long x = s * bit32 + 30 * bit18 + id; sockets[pos++] = -x; for (int adapter = 1; adapter <= 30; adapter++) { if (s == 1) break; s = (s + 1) / 2; long y = s * bit32 + (30 - adapter) * bit18 + id; sockets[pos++] = -y; } } System.err.println(System.currentTimeMillis() - start); Arrays.sort(sockets); System.err.println(System.currentTimeMillis() - start); int c = 0; int adapters = 0; int[] A = new int[M]; int[] B = new int[N]; boolean[] used = new boolean[M]; int cur = 0; for (int[] power : powers) { int p = power[0]; while (cur < pos) { long socket = -sockets[cur]; long s = socket / bit32; if (s < p) break; long adapter = (socket - s * bit32) / bit18; int id = (int) (socket - s * bit32 - adapter * bit18); adapter = 30 - adapter; if (used[id]) { cur++; } else if (s == p) { c++; adapters += adapter; A[id] = (int) adapter; B[power[1]] = id + 1; used[id] = true; cur++; break; } else { cur++; } } } System.err.println(System.currentTimeMillis() - start); StringBuilder builder = new StringBuilder(); builder.append(c).append(" ").append(adapters).append("\n"); for (int i = 0; i < M; i++) { if (i > 0) builder.append(" "); builder.append(A[i]); } builder.append("\n"); for (int i = 0; i < N; i++) { if (i > 0) builder.append(" "); builder.append(B[i]); } builder.append("\n"); out.println(builder.toString()); System.err.println(System.currentTimeMillis() - start); } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) throws Exception { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 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 void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); 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(); } 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(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
