結果
問題 | No.1209 XOR Into You |
ユーザー |
|
提出日時 | 2020-08-30 16:18:34 |
言語 | Java (openjdk 23) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 12,020 bytes |
コンパイル時間 | 3,462 ms |
コンパイル使用メモリ | 97,024 KB |
実行使用メモリ | 50,532 KB |
最終ジャッジ日時 | 2024-11-15 10:56:18 |
合計ジャッジ時間 | 7,599 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 4 |
other | RE * 37 |
ソースコード
import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.util.Arrays;import java.util.function.LongBinaryOperator;import java.util.HashMap;import java.nio.ByteBuffer;import java.nio.charset.Charset;import java.util.Map;import java.util.NoSuchElementException;import java.io.OutputStream;import java.nio.CharBuffer;import java.util.Collection;import java.io.IOException;import java.nio.charset.CharsetDecoder;import java.lang.reflect.Field;import java.nio.charset.StandardCharsets;import java.io.UncheckedIOException;import java.io.Writer;import java.util.Queue;import java.util.ArrayDeque;import java.io.InputStream;/*** Built using CHelper reloaded plug-in* Actual solution is at the top** @author mikit*/public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;LightScanner2 in = new LightScanner2(inputStream);LightWriter2 out = new LightWriter2(outputStream);No1209XORIntoYou solver = new No1209XORIntoYou();solver.solve(1, in, out);out.close();}static class No1209XORIntoYou {public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {int n = in.ints();long[] as = in.longs(n), bs = in.longs(n), a = new long[n - 1], b = new long[n - 1];if (as[0] != bs[0] || as[n - 1] != bs[n - 1]) {out.ans(-1).ln();return;}for (int i = 0; i < n - 1; i++) {a[i] = as[i] ^ as[i + 1];b[i] = bs[i] ^ bs[i + 1];}Map<Long, Queue<Integer>> map = new HashMap<>();for (int i = 0; i < n - 1; i++) {if (!map.containsKey(b[i])) map.put(b[i], new ArrayDeque<>());map.get(b[i]).offer(i);}int[] p = new int[n - 1];for (int i = 0; i < n - 1; i++) {Queue<Integer> q = map.get(a[i]);if (q == null || q.isEmpty()) {out.ans(-1).ln();return;}p[i] = q.poll();}out.ans(InvNum.calcPerm(p)).ln();//out.ans(-1).ln();}}static class LightScanner2 extends LightScannerAdapter {private static final int BUF_SIZE = 32 * 1024;private final InputStream stream;private final StringBuilder builder = new StringBuilder();private final byte[] buf = new byte[BUF_SIZE];private int ptr;private int len;public LightScanner2(InputStream stream) {this.stream = stream;}private int read() {if (ptr < len) return buf[ptr++];try {ptr = 0;len = stream.read(buf);} catch (IOException ex) {throw new UncheckedIOException(ex);}if (len == -1) return -1;return buf[ptr++];}private void skip() {int b;while (isTokenSeparator(b = read()) && b != -1) ;if (b == -1) throw new NoSuchElementException("EOF");ptr--;}private void loadToken() {builder.setLength(0);skip();for (int b = read(); !isTokenSeparator(b); b = read()) {builder.appendCodePoint(b);}}public String string() {loadToken();return builder.toString();}public int ints() {long x = longs();if (x < Integer.MIN_VALUE || Integer.MAX_VALUE < x) throw new NumberFormatException("Overflow");return (int) x;}public long longs() {skip();int b = read();boolean negate;if (b == '-') {negate = true;b = read();} else negate = false;long x = 0;for (; !isTokenSeparator(b); b = read()) {if ('0' <= b && b <= '9') x = x * 10 + b - '0';else throw new NumberFormatException("Unexpected character '" + b + "'");}return negate ? -x : x;}public void close() {try {stream.close();} catch (IOException e) {throw new UncheckedIOException(e);}}private static boolean isTokenSeparator(int b) {return b < 33 || 126 < b;}}static class IntFenwickTree {protected final int n;private final long[] tree;protected final LongBinaryOperator op;protected final long zero;public IntFenwickTree(int n, LongBinaryOperator op, long zero) {this.n = n;tree = new long[n + 1];Arrays.fill(tree, zero);this.op = op;this.zero = zero;}public IntFenwickTree(long[] init, LongBinaryOperator op, long zero) {this(init.length, op, zero);for (int i = 0; i < n; i++) add(i, init[i]);}public void add(int index, long value) {for (index++; index <= n; index += BitMath.extractLsb(index)) {tree[index] = op.applyAsLong(tree[index], value);}}public long query(int last) {long res = zero;for (; last > 0; last -= BitMath.extractLsb(last)) {res = op.applyAsLong(res, tree[last]);}return res;}}static final class BitMath {private BitMath() {}public static int extractLsb(int v) {return v & (-v);}}static class InvNum {private InvNum() {}public static long calcPerm(int[] a) {int n = a.length;IntFenwickTree bit = new IntFenwickTree(n, Long::sum, 0L);long ans = 0;for (int i = n - 1; i >= 0; i--) {ans += bit.query(a[i]);bit.add(a[i], 1);}return ans;}}static class LightWriter2 implements AutoCloseable {private static final int BUF_SIZE = 32 * 1024;private static final int BUF_THRESHOLD = 1024;private final OutputStream out;private final byte[] buf = new byte[BUF_SIZE];private int ptr;private final Field fastStringAccess;private boolean autoflush = false;private boolean breaked = true;public LightWriter2(OutputStream out) {this.out = out;Field f;try {f = String.class.getDeclaredField("value");f.setAccessible(true);if (f.getType() != byte[].class) f = null;} catch (ReflectiveOperationException ignored) {f = null;}this.fastStringAccess = f;}public LightWriter2(Writer out) {this.out = new LightWriter2.WriterOutputStream(out);this.fastStringAccess = null;}private void allocate(int n) {if (ptr + n <= BUF_SIZE) return;try {out.write(buf, 0, ptr);ptr = 0;} catch (IOException ex) {throw new UncheckedIOException(ex);}if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");}public void close() {try {out.write(buf, 0, ptr);ptr = 0;out.flush();out.close();} catch (IOException ex) {throw new UncheckedIOException(ex);}}public LightWriter2 print(char c) {allocate(1);buf[ptr++] = (byte) c;breaked = false;return this;}public LightWriter2 print(String s) {byte[] bytes;if (this.fastStringAccess == null) bytes = s.getBytes();else {try {bytes = (byte[]) fastStringAccess.get(s);} catch (IllegalAccessException ignored) {bytes = s.getBytes();}}int n = bytes.length;if (n <= BUF_THRESHOLD) {allocate(n);System.arraycopy(bytes, 0, buf, ptr, n);ptr += n;return this;}try {out.write(buf, 0, ptr);ptr = 0;out.write(bytes);out.flush();} catch (IOException ex) {throw new UncheckedIOException(ex);}return this;}public LightWriter2 ans(long l) {if (!breaked) {print(' ');}if (l == 0) return print('0');if (l < 0) {print('-');l = -l;}int n = 0;long t = l;while (t > 0) {t /= 10;n++;}allocate(n);for (int i = 1; i <= n; i++) {buf[ptr + n - i] = (byte) (l % 10 + '0');l /= 10;}ptr += n;return this;}public LightWriter2 ans(int i) {if (!breaked) {print(' ');}if (i == 0) return print('0');if (i < 0) {print('-');i = -i;}int n = 0;long t = i;while (t > 0) {t /= 10;n++;}allocate(n);for (int j = 1; j <= n; j++) {buf[ptr + n - j] = (byte) (i % 10 + '0');i /= 10;}ptr += n;return this;}public LightWriter2 ln() {print(System.lineSeparator());breaked = true;if (autoflush) {try {out.flush();} catch (IOException ex) {throw new UncheckedIOException(ex);}}return this;}private static class WriterOutputStream extends OutputStream {final Writer writer;final CharsetDecoder decoder;WriterOutputStream(Writer writer) {this.writer = writer;this.decoder = StandardCharsets.UTF_8.newDecoder();}public void write(int b) throws IOException {writer.write(b);}public void write(byte[] b) throws IOException {writer.write(decoder.decode(ByteBuffer.wrap(b)).array());}public void write(byte[] b, int off, int len) throws IOException {writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());}public void flush() throws IOException {writer.flush();}public void close() throws IOException {writer.close();}}}static abstract class LightScannerAdapter implements AutoCloseable {public abstract String string();public long longs() {return Long.parseLong(string());}public final long[] longs(int length) {long[] res = new long[length];Arrays.setAll(res, ignored -> longs());return res;}public abstract void close();}}