Submission #3070625
Source Code Expand
// package other2015.utpc2014; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.InputMismatchException; import java.util.Map; public class Main { static long __startTime = System.currentTimeMillis(); public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); long a = in.nextLong(); long b = in.nextLong(); long x = in.nextLong(); Map<Long,Integer> smallStep = new HashMap<>(); smallStep.put(a, 0); { long last = a; for (int i = 0; i < 1<<19 ; i++) { long next = nextNaive(last, b); if (!smallStep.containsKey(next)) { smallStep.put(next, i+1); } last = next; } } long[] mat2 = generateMat2(b); long[] matGiantStep = MatrixMod2.pow(mat2, 1<<18); { long last = 0; for (long n = 0; n < (1L << 36); n += (1 << 18)) { long want = last ^ x; if (smallStep.containsKey(want)) { out.println(smallStep.get(want) + n); out.flush(); return; } last = MatrixMod2.mul(matGiantStep, last); } } out.println(-1); out.flush(); } static long[] generateMat2(long b) { long[] matA = new long[40]; for (int i = 0; i < 35 ; i++) { matA[i] = 1L<<(i+1); } long[] matB = new long[40]; for (int i = 0; i < 36; i++) { matB[i] = 1L<<i; } matB[39] = 1; long[] matC = new long[40]; for (int i = 0; i < 40 ; i++) { long has = (b & (1L<<i)) >= 1 ? 1 : 0; matC[i] = has<<39; } return MatrixMod2.add(matA, MatrixMod2.mul(matC, matB)); } static long nextNaive(long a, long b) { return (a / 2) ^ ((a % 2) * b); } public static class MatrixMod2 { static long[] e(int n) { long[] mat = new long[n]; for (int i = 0; i < n ; i++) { mat[i] = 1L<<i; } return mat; } static long[] add(long[] a, long[] b) { long[] c = new long[a.length]; for (int i = 0; i < c.length; i++) { c[i] = a[i] ^ b[i]; } return c; } static long[] flip(long[] a) { long[] r = new long[a.length]; for (int i = 0; i < a.length ; i++) { for (int j = 0; j < a.length ; j++) { r[j] |= ((a[i]&(1L<<j))>>j)<<i; } } return r; } static long[] mul(long[] a, long[] b) { long[] res = new long[a.length]; long[] r = flip(b); for (int i = 0; i < a.length ; i++) { for (int j = 0; j < a.length; j++) { long c = Long.bitCount(a[i] & r[j]) % 2; res[i] |= c<<j; } } return res; } static long mul(long[] a, long b) { long r = 0; for (int i = 0; i < a.length; i++) { long c = Long.bitCount(a[i] & b) % 2; r |= c<<i; } return r; } static long[] pow(long[] x, long p) { int n = x.length; long[] ret = e(n); while (p >= 1) { if ((p & 1) == 1) { ret = mul(ret, x); } x = mul(x, x); p >>>= 1; } return ret; } } private static void printTime(String label) { debug(label, System.currentTimeMillis() - __startTime); } private static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | K - 乱数調整 |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 30 |
Code Size | 6555 Byte |
Status | WA |
Exec Time | 812 ms |
Memory | 110280 KB |
Judge Result
Set Name | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 0 / 270 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 96 ms | 21332 KB |
scrambled_01.txt | AC | 98 ms | 21460 KB |
scrambled_02.txt | AC | 96 ms | 22228 KB |
scrambled_03.txt | AC | 136 ms | 21716 KB |
scrambled_04.txt | AC | 187 ms | 46932 KB |
scrambled_05.txt | AC | 112 ms | 34388 KB |
scrambled_06.txt | AC | 136 ms | 41684 KB |
scrambled_07.txt | AC | 197 ms | 44932 KB |
scrambled_08.txt | AC | 242 ms | 63012 KB |
scrambled_09.txt | AC | 261 ms | 58844 KB |
scrambled_10.txt | AC | 243 ms | 62332 KB |
scrambled_11.txt | AC | 234 ms | 64220 KB |
scrambled_12.txt | AC | 199 ms | 47636 KB |
scrambled_13.txt | AC | 136 ms | 42452 KB |
scrambled_14.txt | AC | 758 ms | 107260 KB |
scrambled_15.txt | AC | 784 ms | 106580 KB |
scrambled_16.txt | AC | 748 ms | 107636 KB |
scrambled_17.txt | AC | 805 ms | 106360 KB |
scrambled_18.txt | WA | 796 ms | 106668 KB |
scrambled_19.txt | WA | 743 ms | 105768 KB |
scrambled_20.txt | WA | 812 ms | 108632 KB |
scrambled_21.txt | WA | 732 ms | 106448 KB |
scrambled_22.txt | WA | 754 ms | 105944 KB |
scrambled_23.txt | WA | 762 ms | 105492 KB |
scrambled_24.txt | WA | 742 ms | 105728 KB |
scrambled_25.txt | WA | 789 ms | 106324 KB |
scrambled_26.txt | WA | 803 ms | 106636 KB |
scrambled_27.txt | WA | 749 ms | 102412 KB |
scrambled_28.txt | AC | 104 ms | 20180 KB |
scrambled_29.txt | AC | 149 ms | 28988 KB |
scrambled_30.txt | AC | 95 ms | 20308 KB |
scrambled_31.txt | AC | 134 ms | 21844 KB |
scrambled_32.txt | AC | 96 ms | 21972 KB |
scrambled_33.txt | AC | 104 ms | 22100 KB |
scrambled_34.txt | AC | 149 ms | 44628 KB |
scrambled_35.txt | AC | 185 ms | 48852 KB |
scrambled_36.txt | AC | 243 ms | 61276 KB |
scrambled_37.txt | AC | 228 ms | 70384 KB |
scrambled_38.txt | WA | 691 ms | 110280 KB |
scrambled_39.txt | WA | 304 ms | 69648 KB |
scrambled_40.txt | WA | 741 ms | 102600 KB |
scrambled_41.txt | WA | 300 ms | 69780 KB |
scrambled_42.txt | WA | 341 ms | 70780 KB |
subtask_00.txt | AC | 146 ms | 36620 KB |
subtask_01.txt | AC | 148 ms | 36916 KB |
subtask_02.txt | AC | 145 ms | 36680 KB |
subtask_03.txt | AC | 147 ms | 33984 KB |
subtask_04.txt | AC | 104 ms | 30804 KB |
subtask_05.txt | AC | 103 ms | 29652 KB |
subtask_06.txt | AC | 107 ms | 30676 KB |
subtask_07.txt | AC | 103 ms | 28756 KB |
subtask_08.txt | AC | 106 ms | 29780 KB |
subtask_09.txt | AC | 101 ms | 25684 KB |
subtask_10.txt | AC | 102 ms | 27604 KB |
subtask_11.txt | AC | 105 ms | 29908 KB |
subtask_12.txt | AC | 104 ms | 27476 KB |
subtask_13.txt | AC | 105 ms | 31700 KB |
subtask_14.txt | AC | 98 ms | 22096 KB |
subtask_15.txt | AC | 136 ms | 19668 KB |
subtask_16.txt | AC | 96 ms | 19412 KB |
subtask_17.txt | AC | 134 ms | 20940 KB |
subtask_18.txt | AC | 95 ms | 19284 KB |
subtask_19.txt | AC | 96 ms | 21332 KB |