Submission #3070770
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(x, 0); { long last = x; long lastA = a; for (int i = 0; i < 1<<18 ; i++) { if (lastA == x) { out.println(i); out.flush(); return; } long next = nextNaive(last, b); lastA = nextNaive(lastA, b); smallStep.put(next, i+1); last = next; } } long[] mat2 = generateMat2(b); long[] matGiantStep = MatrixMod2.pow(mat2, 1<<18); long[] last = MatrixMod2.e(40); long[] going = matGiantStep.clone(); long[][] lstep = new long[(1<<18)+1][]; { for (long n = 1<<18 ; n < (1L << 36); n += (1 << 18)) { if (System.currentTimeMillis() - __startTime >= 1900) { break; } long want = MatrixMod2.mul(going, a); if (smallStep.containsKey(want)) { int idx = smallStep.get(want); long ne = n - smallStep.get(want); int st = (1<<18)-idx; if (verify(MatrixMod2.mul(last, lstep[st]), a, x)) { out.println(ne); out.flush(); return; } } last = going.clone(); going = MatrixMod2.mul(matGiantStep, going); } } out.println(-1); out.flush(); } private static boolean verify(long[] mat2, long a, long x) { return MatrixMod2.mul(mat2, a) == x; } 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[] tmp = new long[40]; 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 | 0 |
Code Size | 7413 Byte |
Status | RE |
Exec Time | 1970 ms |
Memory | 114592 KB |
Judge Result
Set Name | Subtask | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 68 ms | 19412 KB |
scrambled_01.txt | AC | 70 ms | 20180 KB |
scrambled_02.txt | AC | 68 ms | 21460 KB |
scrambled_03.txt | AC | 1939 ms | 65040 KB |
scrambled_04.txt | AC | 114 ms | 26324 KB |
scrambled_05.txt | AC | 75 ms | 18644 KB |
scrambled_06.txt | AC | 102 ms | 22868 KB |
scrambled_07.txt | AC | 112 ms | 24788 KB |
scrambled_08.txt | AC | 174 ms | 51412 KB |
scrambled_09.txt | AC | 164 ms | 53120 KB |
scrambled_10.txt | AC | 124 ms | 35284 KB |
scrambled_11.txt | AC | 114 ms | 22996 KB |
scrambled_12.txt | AC | 124 ms | 27732 KB |
scrambled_13.txt | AC | 96 ms | 21332 KB |
scrambled_14.txt | AC | 1968 ms | 113560 KB |
scrambled_15.txt | AC | 1969 ms | 112640 KB |
scrambled_16.txt | RE | 256 ms | 52404 KB |
scrambled_17.txt | RE | 318 ms | 54228 KB |
scrambled_18.txt | RE | 515 ms | 71672 KB |
scrambled_19.txt | RE | 560 ms | 79340 KB |
scrambled_20.txt | RE | 416 ms | 61660 KB |
scrambled_21.txt | RE | 502 ms | 78216 KB |
scrambled_22.txt | RE | 314 ms | 62996 KB |
scrambled_23.txt | RE | 327 ms | 61296 KB |
scrambled_24.txt | RE | 1251 ms | 110520 KB |
scrambled_25.txt | RE | 255 ms | 53320 KB |
scrambled_26.txt | RE | 588 ms | 77932 KB |
scrambled_27.txt | RE | 846 ms | 81448 KB |
scrambled_28.txt | AC | 71 ms | 22484 KB |
scrambled_29.txt | RE | 117 ms | 23124 KB |
scrambled_30.txt | AC | 70 ms | 19284 KB |
scrambled_31.txt | AC | 1969 ms | 99960 KB |
scrambled_32.txt | AC | 69 ms | 18772 KB |
scrambled_33.txt | AC | 71 ms | 20820 KB |
scrambled_34.txt | AC | 116 ms | 28116 KB |
scrambled_35.txt | AC | 116 ms | 27860 KB |
scrambled_36.txt | AC | 163 ms | 53120 KB |
scrambled_37.txt | RE | 193 ms | 53380 KB |
scrambled_38.txt | RE | 191 ms | 49536 KB |
scrambled_39.txt | WA | 1969 ms | 110216 KB |
scrambled_40.txt | RE | 525 ms | 78900 KB |
scrambled_41.txt | WA | 1970 ms | 114592 KB |
scrambled_42.txt | RE | 1094 ms | 92116 KB |
subtask_00.txt | AC | 1966 ms | 65112 KB |
subtask_01.txt | AC | 1967 ms | 87976 KB |
subtask_02.txt | RE | 134 ms | 34672 KB |
subtask_03.txt | RE | 127 ms | 31956 KB |
subtask_04.txt | AC | 71 ms | 21332 KB |
subtask_05.txt | AC | 70 ms | 20692 KB |
subtask_06.txt | AC | 82 ms | 19796 KB |
subtask_07.txt | AC | 70 ms | 18388 KB |
subtask_08.txt | AC | 82 ms | 20692 KB |
subtask_09.txt | AC | 69 ms | 22740 KB |
subtask_10.txt | AC | 70 ms | 21204 KB |
subtask_11.txt | AC | 69 ms | 19796 KB |
subtask_12.txt | AC | 70 ms | 20436 KB |
subtask_13.txt | AC | 70 ms | 21076 KB |
subtask_14.txt | AC | 71 ms | 18260 KB |
subtask_15.txt | RE | 124 ms | 25684 KB |
subtask_16.txt | AC | 71 ms | 18644 KB |
subtask_17.txt | AC | 1940 ms | 65048 KB |
subtask_18.txt | AC | 70 ms | 22484 KB |
subtask_19.txt | AC | 69 ms | 22612 KB |