結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー | CuriousFairy315 |
提出日時 | 2022-10-14 22:18:00 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 758 ms / 3,000 ms |
コード長 | 11,186 bytes |
コンパイル時間 | 3,801 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 79,416 KB |
最終ジャッジ日時 | 2023-09-08 22:13:19 |
合計ジャッジ時間 | 41,692 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
49,440 KB |
testcase_01 | AC | 42 ms
49,184 KB |
testcase_02 | AC | 485 ms
65,768 KB |
testcase_03 | AC | 528 ms
66,900 KB |
testcase_04 | AC | 450 ms
64,236 KB |
testcase_05 | AC | 364 ms
59,812 KB |
testcase_06 | AC | 478 ms
62,912 KB |
testcase_07 | AC | 441 ms
64,124 KB |
testcase_08 | AC | 246 ms
55,856 KB |
testcase_09 | AC | 484 ms
68,976 KB |
testcase_10 | AC | 311 ms
59,236 KB |
testcase_11 | AC | 264 ms
59,452 KB |
testcase_12 | AC | 383 ms
61,904 KB |
testcase_13 | AC | 541 ms
65,124 KB |
testcase_14 | AC | 415 ms
64,184 KB |
testcase_15 | AC | 517 ms
65,264 KB |
testcase_16 | AC | 630 ms
72,964 KB |
testcase_17 | AC | 333 ms
62,720 KB |
testcase_18 | AC | 469 ms
65,480 KB |
testcase_19 | AC | 333 ms
59,820 KB |
testcase_20 | AC | 587 ms
70,288 KB |
testcase_21 | AC | 297 ms
57,228 KB |
testcase_22 | AC | 711 ms
74,980 KB |
testcase_23 | AC | 672 ms
73,708 KB |
testcase_24 | AC | 691 ms
71,004 KB |
testcase_25 | AC | 745 ms
75,448 KB |
testcase_26 | AC | 699 ms
74,424 KB |
testcase_27 | AC | 698 ms
75,140 KB |
testcase_28 | AC | 676 ms
70,916 KB |
testcase_29 | AC | 700 ms
70,444 KB |
testcase_30 | AC | 688 ms
72,448 KB |
testcase_31 | AC | 684 ms
70,548 KB |
testcase_32 | AC | 754 ms
74,552 KB |
testcase_33 | AC | 686 ms
77,360 KB |
testcase_34 | AC | 698 ms
70,112 KB |
testcase_35 | AC | 758 ms
75,532 KB |
testcase_36 | AC | 706 ms
74,460 KB |
testcase_37 | AC | 721 ms
70,540 KB |
testcase_38 | AC | 682 ms
73,480 KB |
testcase_39 | AC | 745 ms
72,516 KB |
testcase_40 | AC | 665 ms
73,912 KB |
testcase_41 | AC | 680 ms
76,592 KB |
testcase_42 | AC | 519 ms
68,008 KB |
testcase_43 | AC | 533 ms
67,700 KB |
testcase_44 | AC | 526 ms
69,112 KB |
testcase_45 | AC | 530 ms
70,148 KB |
testcase_46 | AC | 519 ms
67,840 KB |
testcase_47 | AC | 457 ms
67,640 KB |
testcase_48 | AC | 437 ms
65,296 KB |
testcase_49 | AC | 445 ms
68,352 KB |
testcase_50 | AC | 451 ms
67,188 KB |
testcase_51 | AC | 468 ms
65,636 KB |
testcase_52 | AC | 206 ms
72,624 KB |
testcase_53 | AC | 212 ms
72,356 KB |
testcase_54 | AC | 205 ms
72,860 KB |
testcase_55 | AC | 320 ms
59,032 KB |
testcase_56 | AC | 317 ms
58,904 KB |
testcase_57 | AC | 317 ms
59,344 KB |
testcase_58 | AC | 276 ms
65,376 KB |
testcase_59 | AC | 682 ms
79,416 KB |
testcase_60 | AC | 253 ms
55,436 KB |
testcase_61 | AC | 320 ms
58,884 KB |
testcase_62 | AC | 137 ms
53,136 KB |
testcase_63 | AC | 366 ms
61,488 KB |
testcase_64 | AC | 359 ms
61,792 KB |
testcase_65 | AC | 374 ms
62,244 KB |
testcase_66 | AC | 330 ms
58,756 KB |
testcase_67 | AC | 381 ms
58,432 KB |
testcase_68 | AC | 284 ms
58,396 KB |
testcase_69 | AC | 376 ms
59,764 KB |
ソースコード
import java.util.HashSet; public class Main { public static void main(String[] args) { new Main(); } public Main() { FastScanner fs = new FastScanner(); java.io.PrintWriter out = new java.io.PrintWriter(System.out); solve(fs, out); out.flush(); } public void solve(FastScanner fs, java.io.PrintWriter out) { int N = fs.nextInt(); HashSet<Long> hash = new HashSet<>(); for (int i = 0;i < N;++ i) { char[] S = fs.next().toCharArray(); RollingHash rh = new RollingHash(S); long self = rh.hash(); boolean ans = !hash.add(self); for (int j = 1;j < S.length;++ j) { long h = rh.hash(0, j - 1); h = RollingHash.mul(h, RollingHash.base); h = RollingHash.mul(h + S[j], RollingHash.base); h = RollingHash.mul(h + S[j - 1], rh.pow[S.length - j - 1]); h = RollingHash.mod(h + rh.hash(j + 1, S.length)); ans |= h != self && hash.contains(h); } out.println(ans ? "Yes" : "No"); } } public static class RollingHash { private final long[] hash; private final long[] pow; public static final long MOD = (1L << 61) - 1; private static final long MASK0 = (1L << 30) - 1; private static final long MASK1 = (1L << 31) - 1; private static long base = -1; private RollingHash(final char[] s) { this(s, base == -1 ? base() : base); } private RollingHash(final char[] s, final long base) { RollingHash.base = base; hash = new long[s.length + 1]; pow = new long[s.length + 1]; pow[0] = 1; for (int i = 0;i < s.length;++ i) { hash[i + 1] = mod(mul(hash[i], base) + s[i]); pow[i + 1] = mul(pow[i], base); } } long hash() { return hash[hash.length - 1]; } long hash(final int l, final int r) { return mod(hash[r] - mul(hash[l], pow[r - l]) + MOD); } private static long mul(final long a, final long b) { final long au = a >>> 31; final long ad = a & MASK1; final long bu = b >>> 31; final long bd = b & MASK1; final long mid = ad * bu + au * bd; final long midu = mid >>> 30; final long midd = mid & MASK0; return mod((au * bu << 1) + midu + (midd << 31) + ad * bd); } private static long mod(final long x) { final long xu = x >>> 61; final long xd = x & MOD; long res = xu + xd; if (res >= MOD) res -= MOD; return res; } public static long base() { return base(new java.util.Random()); } public static long base(final java.util.Random rnd) { while(true) { long e = mod(rnd.nextLong()); if (gcd(e, MOD - 1) == 1) { long ans = 1; for (long mul = 37; e > 0; e >>= 1, mul = mul(mul, mul)) if ((e & 1) != 0) ans = mul(ans, mul); return ans; } } } private static long gcd(long a, long b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } } final int MOD = 998_244_353; int plus(int n, int m) { int sum = n + m; if (sum >= MOD) sum -= MOD; return sum; } int minus(int n, int m) { int sum = n - m; if (sum < 0) sum += MOD; return sum; } int times(int n, int m) { return (int)((long)n * m % MOD); } int divide(int n, int m) { return times(n, IntMath.pow(m, MOD - 2, MOD)); } int[] fact, invf; void calc(int len) { len += 2; fact = new int[len]; invf = new int[len]; fact[0] = fact[1] = invf[0] = invf[1] = 1; for (int i = 2;i < fact.length;++ i) fact[i] = times(fact[i - 1], i); invf[len - 1] = divide(1, fact[len - 1]); for (int i = len - 1;i > 1;-- i) invf[i - 1] = times(i, invf[i]); } int comb(int n, int m) { if (n < m) return 0; return times(fact[n], times(invf[n - m], invf[m])); } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] buffer = new byte[8192]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (java.io.IOException e) { e.printStackTrace(); } return buflen > 0; } private byte readByte() { return hasNextByte() ? buffer[ptr++ ] : -1; } private static boolean isPrintableChar(byte c) { return 32 < c || c < 0; } private static boolean isNumber(int c) { return '0' <= c && c <= '9'; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++ ; return hasNextByte(); } public String next() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); byte b; while (isPrintableChar(b = readByte())) sb.appendCodePoint(b); return sb.toString(); } public final char nextChar() { if (!hasNext()) throw new java.util.NoSuchElementException(); return (char)readByte(); } public final long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public final int nextInt() { if (!hasNext()) throw new java.util.NoSuchElementException(); int n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public double nextDouble() { return Double.parseDouble(next()); } } class Arrays { public static void sort(final int[] array) { sort(array, 0, array.length); } public static void sort(final int[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new int[array.length]); } private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) { if (to - from <= 512) { java.util.Arrays.sort(a, from, to); return; } final int BUCKET_SIZE = 256; final int INT_RECURSION = 4; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(a[i] >>> shift & MASK) + 1]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = a[i] >>> shift & MASK; bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < INT_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void sort(final long[] array) { sort(array, 0, array.length); } public static void sort(final long[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new long[array.length]); } private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) { final int BUCKET_SIZE = 256; final int LONG_RECURSION = 8; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(int) ((a[i] >>> shift & MASK) + 1)]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = (int) (a[i] >>> shift & MASK); bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < LONG_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void reverse(int[] array) { reverse(array, 0, array.length); } public static void reverse(int[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { int swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void reverse(long[] array) { reverse(array, 0, array.length); } public static void reverse(long[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { long swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void shuffle(int[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; int swap = array[i]; array[i] = array[j]; array[j] = swap; } } public static void shuffle(long[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; long swap = array[i]; array[i] = array[j]; array[j] = swap; } } } class IntMath { public static int gcd(int a, int b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static int gcd(int... array) { int ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long gcd(long a, long b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static long gcd(long... array) { long ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long lcm(long a, long b) { return a / gcd(a, b) * b; } public static int pow(int a, int b) { int ans = 1; for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static long pow(long a, long b) { long ans = 1; for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static int pow(int a, long b, int mod) { if (b < 0) b = b % (mod - 1) + mod - 1; long ans = 1; for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod; return (int)ans; } public static int pow(long a, long b, int mod) { return pow((int)(a % mod), b, mod); } public static int floorsqrt(long n) { return (int)Math.sqrt(n + 0.1); } public static int ceilsqrt(long n) { return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1; } }