結果
問題 | No.590 Replacement |
ユーザー | 👑 hos.lyric |
提出日時 | 2019-01-26 16:33:45 |
言語 | D (dmd 2.106.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,912 bytes |
コンパイル時間 | 1,153 ms |
コンパイル使用メモリ | 120,244 KB |
実行使用メモリ | 19,412 KB |
最終ジャッジ日時 | 2023-09-03 23:08:06 |
合計ジャッジ時間 | 6,578 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 6 ms
4,912 KB |
testcase_08 | AC | 4 ms
4,380 KB |
testcase_09 | AC | 7 ms
4,384 KB |
testcase_10 | AC | 4 ms
4,916 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 7 ms
5,104 KB |
testcase_13 | AC | 33 ms
6,900 KB |
testcase_14 | AC | 48 ms
8,616 KB |
testcase_15 | AC | 4 ms
4,380 KB |
testcase_16 | AC | 13 ms
6,336 KB |
testcase_17 | AC | 21 ms
6,052 KB |
testcase_18 | AC | 76 ms
14,048 KB |
testcase_19 | AC | 75 ms
14,004 KB |
testcase_20 | AC | 19 ms
6,024 KB |
testcase_21 | AC | 90 ms
18,276 KB |
testcase_22 | AC | 86 ms
18,584 KB |
testcase_23 | AC | 93 ms
17,008 KB |
testcase_24 | AC | 94 ms
18,252 KB |
testcase_25 | AC | 96 ms
17,044 KB |
testcase_26 | AC | 95 ms
18,708 KB |
testcase_27 | AC | 93 ms
18,928 KB |
testcase_28 | AC | 98 ms
17,044 KB |
testcase_29 | AC | 98 ms
17,324 KB |
testcase_30 | AC | 97 ms
18,432 KB |
testcase_31 | AC | 94 ms
16,856 KB |
testcase_32 | AC | 92 ms
16,956 KB |
testcase_33 | AC | 2 ms
4,376 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,376 KB |
testcase_36 | AC | 74 ms
18,404 KB |
testcase_37 | AC | 76 ms
17,872 KB |
testcase_38 | AC | 70 ms
16,944 KB |
testcase_39 | AC | 71 ms
16,340 KB |
testcase_40 | AC | 100 ms
17,360 KB |
testcase_41 | AC | 99 ms
17,472 KB |
testcase_42 | AC | 88 ms
18,452 KB |
testcase_43 | AC | 89 ms
17,764 KB |
testcase_44 | AC | 73 ms
17,404 KB |
testcase_45 | WA | - |
testcase_46 | WA | - |
コンパイルメッセージ
/dmd2/linux/bin64/../../src/phobos/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } Int mod(Int)(Int a, Int m) { if ((a %= m) < 0) a += m; return a; } Int gojo(Int)(Int a, Int b, out Int x, out Int y) { if (b != 0) { Int g = gojo(b, a % b, y, x); y -= (a / b) * x; return g; } x = 1; y = 0; return a; } enum MO = 10L^^9 + 7; void main() { try { for (; ; ) { const N = readInt(); auto A = new int[][](2, N); foreach (h; 0 .. 2) { foreach (i; 0 .. N) { A[h][i] = readInt() - 1; } } auto lens = new long[][](2, N); auto rprs = new int[][](2, N); auto poss = new long[][](2, N); foreach (h; 0 .. 2) { auto vis = new bool[N]; foreach (i; 0 .. N) { if (!vis[i]) { for (int j = i; !vis[j]; j = A[h][j]) { vis[j] = true; rprs[h][j] = i; poss[h][j] = lens[h][i]++; } } } } debug { writeln("lens = ", lens); writeln("rprs = ", rprs); writeln("poss = ", poss); } auto entries = new Tuple!(int, int, long, int)[N]; foreach (i; 0 .. N) { const m0 = lens[0][rprs[0][i]]; const m1 = lens[1][rprs[1][i]]; const g = gcd(m0, m1); entries[i] = tuple(rprs[0][i], rprs[1][i], mod(poss[1][i] - poss[0][i], g), i); } entries.sort; long ans; for (int a = 0, b = 0; a < N; a = b) { for (; b < N && entries[a][0 .. 3] == entries[b][0 .. 3]; ++b) {} const m0 = lens[0][entries[a][0]]; const m1 = lens[1][entries[a][1]]; const d = entries[a][2]; long x, y; const g = gojo(m0, m1, x, y); const mm = m0 * (m1 / g); debug { writeln("entries[a .. b] = ", entries[a .. b]); writefln("m0 = %s, m1 = %s, g = %s, x = %s, y = %s", m0, m1, g, x, y); } long[] ts; foreach (c; a .. b) { const i = entries[c][3]; debug { writefln(" %s: (%s, %s)", i, poss[0][i], poss[1][i]); } /* t == poss[0][i] (m0) d + t == poss[1][i] (m1) */ const t0 = poss[0][i]; const t1 = mod(poss[1][i] - d, m1); assert((t1 - t0) % g == 0); const t = mod(t0 + m0 * ((x * ((t1 - t0) / g)) % (m1 / g)), mm); assert(t % m0 == poss[0][i]); assert((d + t) % m1 == poss[1][i]); ts ~= t; } ts.sort; debug { writeln(" ts = ", ts); } foreach (j; 0 .. ts.length) { long k = mod(ts[(j + 1) % $] - ts[j], mm); if (k == 0) { k = mm; } ans += k * (k - 1) / 2; } } ans %= MO; writeln(ans); } } catch (EOFException e) { } }