結果
問題 | No.5015 Escape from Labyrinth |
ユーザー | yupiteru_kun |
提出日時 | 2023-04-16 01:16:12 |
言語 | C# (.NET 8.0.203) |
結果 |
WA
|
実行時間 | - |
コード長 | 39,399 bytes |
コンパイル時間 | 9,000 ms |
コンパイル使用メモリ | 145,564 KB |
実行使用メモリ | 76,348 KB |
スコア | 172,850 |
最終ジャッジ日時 | 2023-04-16 01:20:56 |
合計ジャッジ時間 | 271,962 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,583 ms
63,204 KB |
testcase_01 | AC | 2,579 ms
61,300 KB |
testcase_02 | AC | 2,502 ms
60,916 KB |
testcase_03 | AC | 2,752 ms
70,828 KB |
testcase_04 | AC | 2,514 ms
61,048 KB |
testcase_05 | AC | 2,789 ms
72,364 KB |
testcase_06 | AC | 2,813 ms
71,356 KB |
testcase_07 | AC | 2,641 ms
65,864 KB |
testcase_08 | AC | 2,628 ms
61,732 KB |
testcase_09 | AC | 2,508 ms
60,720 KB |
testcase_10 | AC | 2,540 ms
63,308 KB |
testcase_11 | AC | 2,834 ms
72,748 KB |
testcase_12 | AC | 2,530 ms
63,372 KB |
testcase_13 | AC | 2,668 ms
62,252 KB |
testcase_14 | AC | 2,581 ms
62,768 KB |
testcase_15 | AC | 2,743 ms
70,176 KB |
testcase_16 | AC | 2,621 ms
62,088 KB |
testcase_17 | AC | 2,766 ms
67,304 KB |
testcase_18 | AC | 2,503 ms
61,004 KB |
testcase_19 | AC | 2,811 ms
73,816 KB |
testcase_20 | AC | 2,608 ms
63,828 KB |
testcase_21 | AC | 2,583 ms
63,216 KB |
testcase_22 | AC | 2,791 ms
71,920 KB |
testcase_23 | AC | 2,783 ms
73,896 KB |
testcase_24 | AC | 2,516 ms
61,164 KB |
testcase_25 | AC | 2,797 ms
73,472 KB |
testcase_26 | AC | 2,769 ms
73,664 KB |
testcase_27 | AC | 2,500 ms
60,884 KB |
testcase_28 | AC | 2,594 ms
61,324 KB |
testcase_29 | AC | 2,708 ms
67,896 KB |
testcase_30 | AC | 2,784 ms
71,884 KB |
testcase_31 | AC | 2,831 ms
74,692 KB |
testcase_32 | AC | 2,411 ms
61,900 KB |
testcase_33 | AC | 2,778 ms
71,988 KB |
testcase_34 | AC | 2,483 ms
60,784 KB |
testcase_35 | AC | 2,602 ms
61,688 KB |
testcase_36 | AC | 2,875 ms
75,756 KB |
testcase_37 | AC | 2,848 ms
74,456 KB |
testcase_38 | AC | 2,633 ms
63,836 KB |
testcase_39 | AC | 2,585 ms
61,176 KB |
testcase_40 | AC | 2,797 ms
71,508 KB |
testcase_41 | AC | 2,575 ms
63,220 KB |
testcase_42 | AC | 2,507 ms
60,516 KB |
testcase_43 | AC | 2,794 ms
69,456 KB |
testcase_44 | AC | 2,549 ms
62,380 KB |
testcase_45 | AC | 2,788 ms
71,756 KB |
testcase_46 | AC | 2,547 ms
61,436 KB |
testcase_47 | AC | 2,736 ms
65,048 KB |
testcase_48 | AC | 2,845 ms
76,148 KB |
testcase_49 | AC | 2,508 ms
62,916 KB |
testcase_50 | AC | 2,781 ms
70,428 KB |
testcase_51 | AC | 2,793 ms
71,272 KB |
testcase_52 | AC | 2,560 ms
61,468 KB |
testcase_53 | AC | 2,525 ms
61,072 KB |
testcase_54 | AC | 2,615 ms
61,744 KB |
testcase_55 | AC | 2,560 ms
61,160 KB |
testcase_56 | AC | 2,782 ms
70,696 KB |
testcase_57 | AC | 2,480 ms
58,448 KB |
testcase_58 | AC | 2,813 ms
69,236 KB |
testcase_59 | AC | 2,587 ms
59,824 KB |
testcase_60 | AC | 2,665 ms
60,108 KB |
testcase_61 | AC | 2,809 ms
68,984 KB |
testcase_62 | AC | 2,741 ms
66,836 KB |
testcase_63 | AC | 2,630 ms
59,656 KB |
testcase_64 | AC | 2,461 ms
58,472 KB |
testcase_65 | AC | 2,721 ms
59,732 KB |
testcase_66 | AC | 2,605 ms
59,868 KB |
testcase_67 | AC | 2,629 ms
61,948 KB |
testcase_68 | AC | 2,557 ms
60,900 KB |
testcase_69 | AC | 2,738 ms
71,288 KB |
testcase_70 | AC | 2,648 ms
61,572 KB |
testcase_71 | AC | 2,769 ms
72,772 KB |
testcase_72 | AC | 2,487 ms
62,812 KB |
testcase_73 | AC | 2,814 ms
71,596 KB |
testcase_74 | AC | 2,605 ms
61,584 KB |
testcase_75 | AC | 2,722 ms
70,232 KB |
testcase_76 | AC | 2,817 ms
70,836 KB |
testcase_77 | AC | 2,631 ms
61,900 KB |
testcase_78 | AC | 2,814 ms
71,004 KB |
testcase_79 | AC | 2,583 ms
61,540 KB |
testcase_80 | AC | 2,535 ms
60,776 KB |
testcase_81 | AC | 2,650 ms
62,016 KB |
testcase_82 | AC | 2,524 ms
61,340 KB |
testcase_83 | AC | 2,801 ms
71,516 KB |
testcase_84 | AC | 2,803 ms
72,952 KB |
testcase_85 | AC | 2,536 ms
60,840 KB |
testcase_86 | AC | 2,819 ms
70,872 KB |
testcase_87 | AC | 2,609 ms
61,648 KB |
testcase_88 | AC | 2,592 ms
61,824 KB |
testcase_89 | AC | 2,768 ms
68,840 KB |
testcase_90 | AC | 2,624 ms
61,596 KB |
testcase_91 | AC | 2,789 ms
71,912 KB |
testcase_92 | WA | - |
testcase_93 | AC | 2,766 ms
72,596 KB |
testcase_94 | AC | 2,789 ms
67,296 KB |
testcase_95 | AC | 2,582 ms
65,496 KB |
testcase_96 | AC | 2,792 ms
72,656 KB |
testcase_97 | AC | 2,761 ms
70,840 KB |
testcase_98 | AC | 2,628 ms
62,020 KB |
testcase_99 | AC | 2,763 ms
76,348 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 120 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using System; using System.Collections.Generic; using System.IO; using System.Linq; using static System.Math; using System.Text; using System.Threading; using System.Globalization; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Library; namespace Program { public static class ProblemA { static bool SAIKI = false; static public int numberOfRandomCases = 0; static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker) { } static public void Solve() { var N = (int)NN; var D = (int)NN; var H = (int)NN; var S = NSList(N); var M = (int)NN; var yxd = Repeat(0, M).Select(_ => new { y = (int)NN, x = (int)NN, d = (int)NN }).ToArray(); var fieldItem = new int[N, N]; const int JEWEL = 10000; const int WALL = 20000; const int ENEMY = 30000; const int FIRE = 40000; var jewelNum = 0; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { switch (S[i][j]) { case '#': fieldItem[i, j] = WALL; break; case 'J': fieldItem[i, j] = ++jewelNum; break; case 'E': fieldItem[i, j] = ENEMY; break; case 'F': fieldItem[i, j] = FIRE; break; } } } var startX = 0; var startY = 0; var keyX = 0; var keyY = 0; var goalX = 0; var goalY = 0; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { if (S[i][j] == 'S') { startY = i; startX = j; } if (S[i][j] == 'G') { goalY = i; goalX = j; } if (S[i][j] == 'K') { keyY = i; keyX = j; } } } var diff_start_key = Abs(startY - keyY) + Abs(startX - keyX); var diff_start_goal = Abs(startY - goalY) + Abs(startX - goalX); var diff_key_goal = Abs(keyY - goalY) + Abs(keyX - goalX); var effect = new List<int>[N, N]; for (var i = 0; i < N; ++i) for (var j = 0; j < N; ++j) effect[i, j] = new List<int>(); var tantiki = new int[N, N]; tantiki.Fill(-1); for (var i = 0; i < M; ++i) tantiki[yxd[i].y, yxd[i].x] = i; for (var i = 0; i < N; ++i) { var before = -1; for (var j = 0; j < N; ++j) { if (before != -1) effect[i, j].Add(before); if (tantiki[i, j] != -1) before = tantiki[i, j]; if (fieldItem[i, j] == WALL) before = -1; } before = -1; for (var j = N - 1; j >= 0; --j) { if (before != -1) effect[i, j].Add(before); if (tantiki[i, j] != -1) before = tantiki[i, j]; if (fieldItem[i, j] == WALL) before = -1; } } for (var j = 0; j < N; ++j) { var before = -1; for (var i = 0; i < N; ++i) { if (before != -1) effect[i, j].Add(before); if (tantiki[i, j] != -1) before = tantiki[i, j]; if (fieldItem[i, j] == WALL) before = -1; } before = -1; for (var i = N - 1; i >= 0; --i) { if (before != -1) effect[i, j].Add(before); if (tantiki[i, j] != -1) before = tantiki[i, j]; if (fieldItem[i, j] == WALL) before = -1; } } if (diff_start_key > diff_key_goal) { var pool1 = new List<LIB_Bitset>(10000); var pool2 = new List<LIB_Bitset>(10000); Func<int, int, double, bool, (int lastHealth, int count, string[], int turn)> calc = (startTurn, startHelath, gain, dry) => { var dp = new (double health, int count, LIB_Bitset got)[N, N]; var ndp = new (double health, int count, LIB_Bitset got)[N, N]; var ansField = new List<string[,]>(); dp[startY, startX] = (startHelath, 0, new LIB_Bitset(jewelNum + 1)); var maxH = 0.0; var maxCount = 0; var finishTurn = 0; for (var turn = startTurn; turn < 1000; ++turn) { ndp.Fill((0, 0, null)); string[,] ans = null; if (!dry) ans = new string[N, N]; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { if (fieldItem[i, j] == WALL || fieldItem[i, j] == ENEMY) continue; var nh = dp[i, j].health; var ope = "S"; var count = dp[i, j].count; var got = dp[i, j].got; if (!(got is null)) pool2.Add(got); if (i > 0 && nh.Chmax(dp[i - 1, j].health)) { ope = "M D"; count = dp[i - 1, j].count; got = dp[i - 1, j].got; } if (i < N - 1 && nh.Chmax(dp[i + 1, j].health)) { ope = "M U"; count = dp[i + 1, j].count; got = dp[i + 1, j].got; } if (j > 0 && nh.Chmax(dp[i, j - 1].health)) { ope = "M R"; count = dp[i, j - 1].count; got = dp[i, j - 1].got; } if (j < N - 1 && nh.Chmax(dp[i, j + 1].health)) { ope = "M L"; count = dp[i, j + 1].count; got = dp[i, j + 1].got; } nh -= 1; foreach (var item in effect[i, j]) { if (turn % yxd[item].d == 0) nh -= D; } if (nh <= 0) continue; if (pool1.Count > 0) { var nextgot = pool1[pool1.Count - 1]; pool1.RemoveAt(pool1.Count - 1); for (var k = 0; k < nextgot.ary.Length; ++k) { nextgot.ary[k] = got.ary[k]; } got = nextgot; } else { got = got | 0; } if (0 < fieldItem[i, j] && fieldItem[i, j] <= JEWEL && !got[fieldItem[i, j]]) { nh += gain; ++count; got[fieldItem[i, j]] = true; } ndp[i, j] = (nh, count, got); if (!dry) ans[i, j] = ope; } } var t = dp; dp = ndp; ndp = t; var t3 = pool1; pool1 = pool2; pool2 = t3; if (maxH.Chmax(dp[keyY, keyX].health)) { maxCount = dp[keyY, keyX].count; finishTurn = ansField.Count; } ansField.Add(ans); } var firstAnswer = new List<string>(); if (!dry) { var nowx = keyX; var nowy = keyY; for (var turn = finishTurn; turn >= 0; --turn) { var ope = ansField[turn][nowy, nowx]; firstAnswer.Add(ope); if (ope == "M D") --nowy; else if (ope == "M U") ++nowy; else if (ope == "M R") --nowx; else if (ope == "M L") ++nowx; } firstAnswer.Reverse(); } return ((int)maxH, maxCount, firstAnswer.ToArray(), finishTurn + 1); }; { var left = 8.0; var right = 12.0; var gain = 0.0; var minokgain = double.MaxValue; for (var count = 0; count < 5; ++count) { var mid = (right + left) / 2; var res = calc(1, H, mid, true); var hp = res.lastHealth - res.count * mid; if (hp < diff_key_goal * 3) right = mid; else { left = mid; if (minokgain.Chmin(hp)) gain = mid; } } var ans = calc(1, H, gain, false); var dp = new int[N, N]; var ndp = new int[N, N]; var ansField = new List<string[,]>(); dp[keyY, keyX] = (int)(ans.lastHealth - ans.count * gain); var finishTurn = 0; var maxH = 0; for (var turn = ans.turn + 1; turn < 1000; ++turn) { ndp.Fill(0); var ans2 = new string[N, N]; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { if (fieldItem[i, j] == WALL || fieldItem[i, j] == ENEMY) continue; var nh = dp[i, j]; var ope = "S"; if (i > 0 && nh.Chmax(dp[i - 1, j])) ope = "M D"; if (i < N - 1 && nh.Chmax(dp[i + 1, j])) ope = "M U"; if (j > 0 && nh.Chmax(dp[i, j - 1])) ope = "M R"; if (j < N - 1 && nh.Chmax(dp[i, j + 1])) ope = "M L"; --nh; foreach (var item in effect[i, j]) { if (turn % yxd[item].d == 0) { nh -= D; } } ndp[i, j] = nh; ans2[i, j] = ope; } } var t = dp; dp = ndp; ndp = t; if (maxH.Chmax(dp[goalY, goalX])) finishTurn = turn; ansField.Add(ans2); } var firstAnswer = new List<string>(); { var nowx = goalX; var nowy = goalY; for (var turn = finishTurn - ans.turn - 1; turn >= 0; --turn) { var ope = ansField[turn][nowy, nowx]; firstAnswer.Add(ope); if (ope == "M D") --nowy; else if (ope == "M U") ++nowy; else if (ope == "M R") --nowx; else if (ope == "M L") ++nowx; } firstAnswer.Reverse(); } foreach (var item in ans.Item3) { Console.WriteLine(item); } foreach (var item in firstAnswer) { Console.WriteLine(item); } } } else { var dp = new int[N, N]; var ndp = new int[N, N]; var ansField = new List<string[,]>(); dp[startY, startX] = H; var finishTurn = 0; var maxH = 0; for (var turn = 1; turn < 500; ++turn) { ndp.Fill(0); var ans = new string[N, N]; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { if (fieldItem[i, j] == WALL || fieldItem[i, j] == ENEMY) continue; var nh = dp[i, j]; var ope = "S"; if (i > 0 && nh.Chmax(dp[i - 1, j])) ope = "M D"; if (i < N - 1 && nh.Chmax(dp[i + 1, j])) ope = "M U"; if (j > 0 && nh.Chmax(dp[i, j - 1])) ope = "M R"; if (j < N - 1 && nh.Chmax(dp[i, j + 1])) ope = "M L"; --nh; foreach (var item in effect[i, j]) { if (turn % yxd[item].d == 0) { nh -= D; } } ndp[i, j] = nh; ans[i, j] = ope; } } var t = dp; dp = ndp; ndp = t; if (maxH.Chmax(dp[keyY, keyX])) finishTurn = turn; ansField.Add(ans); } var firstAnswer = new List<string>(); { var nowx = keyX; var nowy = keyY; for (var turn = finishTurn - 1; turn >= 0; --turn) { var ope = ansField[turn][nowy, nowx]; firstAnswer.Add(ope); if (ope == "M D") --nowy; else if (ope == "M U") ++nowy; else if (ope == "M R") --nowx; else if (ope == "M L") ++nowx; if (fieldItem[nowy, nowx] <= JEWEL) fieldItem[nowy, nowx] = 0; } firstAnswer.Reverse(); } var pool1 = new List<LIB_Bitset>(10000); var pool2 = new List<LIB_Bitset>(10000); Func<int, int, double, bool, (int lastHealth, int count, string[])> calc = (startTurn, startHelath, gain, dry) => { var dp = new (double health, int count, LIB_Bitset got)[N, N]; var ndp = new (double health, int count, LIB_Bitset got)[N, N]; var ansField = new List<string[,]>(); dp[keyY, keyX] = (startHelath, 0, new LIB_Bitset(jewelNum + 1)); var maxH = 0.0; var maxCount = 0; var finishTurn = 0; for (var turn = startTurn; turn < 1000; ++turn) { ndp.Fill((0, 0, null)); string[,] ans = null; if (!dry) ans = new string[N, N]; for (var i = 0; i < N; ++i) { for (var j = 0; j < N; ++j) { if (fieldItem[i, j] == WALL || fieldItem[i, j] == ENEMY) continue; var nh = dp[i, j].health; var ope = "S"; var count = dp[i, j].count; var got = dp[i, j].got; if (!(got is null)) pool2.Add(got); if (i > 0 && nh.Chmax(dp[i - 1, j].health)) { ope = "M D"; count = dp[i - 1, j].count; got = dp[i - 1, j].got; } if (i < N - 1 && nh.Chmax(dp[i + 1, j].health)) { ope = "M U"; count = dp[i + 1, j].count; got = dp[i + 1, j].got; } if (j > 0 && nh.Chmax(dp[i, j - 1].health)) { ope = "M R"; count = dp[i, j - 1].count; got = dp[i, j - 1].got; } if (j < N - 1 && nh.Chmax(dp[i, j + 1].health)) { ope = "M L"; count = dp[i, j + 1].count; got = dp[i, j + 1].got; } nh -= 1; foreach (var item in effect[i, j]) { if (turn % yxd[item].d == 0) nh -= D; } if (nh <= 0) continue; if (pool1.Count > 0) { var nextgot = pool1[pool1.Count - 1]; pool1.RemoveAt(pool1.Count - 1); for (var k = 0; k < nextgot.ary.Length; ++k) { nextgot.ary[k] = got.ary[k]; } got = nextgot; } else { got = got | 0; } if (0 < fieldItem[i, j] && fieldItem[i, j] <= JEWEL && !got[fieldItem[i, j]]) { nh += gain; ++count; got[fieldItem[i, j]] = true; } ndp[i, j] = (nh, count, got); if (!dry) ans[i, j] = ope; } } var t = dp; dp = ndp; ndp = t; var t3 = pool1; pool1 = pool2; pool2 = t3; if (maxH.Chmax(dp[goalY, goalX].health)) { maxCount = dp[goalY, goalX].count; finishTurn = ansField.Count; } ansField.Add(ans); } var firstAnswer = new List<string>(); if (!dry) { var nowx = goalX; var nowy = goalY; for (var turn = finishTurn; turn >= 0; --turn) { var ope = ansField[turn][nowy, nowx]; firstAnswer.Add(ope); if (ope == "M D") --nowy; else if (ope == "M U") ++nowy; else if (ope == "M R") --nowx; else if (ope == "M L") ++nowx; } firstAnswer.Reverse(); } return ((int)maxH, maxCount, firstAnswer.ToArray()); }; { var left = 8.0; var right = 12.0; var minokgain = double.MaxValue; var gain = 0.0; for (var count = 0; count < 5; ++count) { var mid = (right + left) / 2; var res = calc(finishTurn + 1, maxH, mid, true); var hp = res.lastHealth - res.count * mid; if (hp < 0) right = mid; else { left = mid; if (minokgain.Chmin(hp)) gain = mid; } } var ans = calc(finishTurn + 1, maxH, gain, false); foreach (var item in firstAnswer) { Console.WriteLine(item); } foreach (var item in ans.Item3) { Console.WriteLine(item); } } } } class Printer : StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; } public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; } } static LIB_FastIO fastio = new LIB_FastIODebug(); static string[] args; static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); } static long NN => fastio.Long(); static double ND => fastio.Double(); static string NS => fastio.Scan(); static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray(); static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray(); static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray(); static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred); static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n); static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c); static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector); static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase); static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } } static IEnumerator<uint> _xsi = _xsc(); static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } } static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; } static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; } static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value); static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value); } } namespace Library { class LIB_FastIO { [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIO() { str = Console.OpenStandardInput(); } readonly Stream str; readonly byte[] buf = new byte[2048]; int len, ptr; [MethodImpl(MethodImplOptions.AggressiveInlining)] byte read() { if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 2048)) <= 0) { return 0; } } return buf[ptr++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public long Long() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = (ret << 3) + (ret << 1) + b - '0'; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } } class LIB_FastIODebug : LIB_FastIO { Queue<string> param = new Queue<string>(); [MethodImpl(MethodImplOptions.AggressiveInlining)] string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIODebug() { } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string Scan() => NextString(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override long Long() => long.Parse(NextString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override double Double() => double.Parse(NextString()); } class LIB_Bitset : IEquatable<LIB_Bitset> { long n; public ulong[] ary; static readonly ulong[] ceil; static LIB_Bitset() { ceil = new ulong[64]; ceil[0] = 0xffffffffffffffff; ceil[1] = 1; for (var i = 2; i < 64; i++) { ceil[i] = (ceil[i - 1] << 1) | 1; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_Bitset(long size) { if (size <= 0) throw new Exception(); n = size; ary = new ulong[((n - 1) >> 6) + 1]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_Bitset(LIB_Bitset src) { n = src.n; ary = src.ary.ToArray(); } public long Count => n; public long PopCount => ary.Sum(e => LIB_BitUtil.PopCount(e)); public bool this[int idx] { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return LIB_BitUtil.IsSet(ary[idx >> 6], idx & 63); } [MethodImpl(MethodImplOptions.AggressiveInlining)] set { if (value) ary[idx >> 6] |= LIB_BitUtil.BitMask[idx & 63]; else ary[idx >> 6] &= ~LIB_BitUtil.BitMask[idx & 63]; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator &(LIB_Bitset x, LIB_Bitset y) { if (x.n < y.n) { var t = x; x = y; y = t; } var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; for (var i = 0; i < y.ary.Length; i++) ret.ary[i] &= y.ary[i]; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator |(LIB_Bitset x, LIB_Bitset y) { if (x.n < y.n) { var t = x; x = y; y = t; } var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; for (var i = 0; i < y.ary.Length; i++) ret.ary[i] |= y.ary[i]; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void OrEqual(LIB_Bitset y) { if (n < y.n) { n = y.n; var tmp = new ulong[y.n]; for (var i = 0; i < ary.Length; i++) tmp[i] = ary[i]; ary = tmp; } for (var i = 0; i < y.ary.Length; i++) ary[i] |= y.ary[i]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator ^(LIB_Bitset x, LIB_Bitset y) { if (x.n < y.n) { var t = x; x = y; y = t; } var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; for (var i = 0; i < y.ary.Length; i++) ret.ary[i] ^= y.ary[i]; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator &(LIB_Bitset x, long y) { var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; ret.ary[0] &= (ulong)y; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator |(LIB_Bitset x, long y) { var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; ret.ary[0] |= (ulong)y; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator ^(LIB_Bitset x, long y) { var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = x.ary[i]; ret.ary[0] ^= (ulong)y; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Flip() { for (var i = 0; i < ary.Length; i++) ary[i] = ~ary[i]; ary[ary.Length - 1] &= ceil[n & 63]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator ~(LIB_Bitset x) { var ret = new LIB_Bitset(x.n); for (var i = 0; i < ret.ary.Length; i++) ret.ary[i] = ~x.ary[i]; ret.ary[ret.ary.Length - 1] &= ceil[ret.n & 63]; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void ShiftLeft(int num) { var moveCnt = num >> 6; var moveBit = num & 63; var i = ary.Length - 1; for (; i >= moveCnt; i--) { ary[i] = ary[i - moveCnt] << moveBit; if (moveBit > 0 && i > moveCnt) ary[i] |= ary[i - moveCnt - 1] >> (64 - moveBit); } for (; i >= 0; --i) ary[i] = 0; ary[ary.Length - 1] &= ceil[n & 63]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator <<(LIB_Bitset x, int num) { var ret = new LIB_Bitset(x.n); var moveCnt = num >> 6; var moveBit = num & 63; var i = ret.ary.Length - 1; for (; i >= moveCnt; i--) { ret.ary[i] = x.ary[i - moveCnt] << moveBit; if (moveBit > 0 && i > moveCnt) ret.ary[i] |= x.ary[i - moveCnt - 1] >> (64 - moveBit); } for (; i >= 0; --i) ret.ary[i] = 0; ret.ary[ret.ary.Length - 1] &= ceil[ret.n & 63]; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void ShiftRight(int num) { var moveCnt = num >> 6; var moveBit = num & 63; var aryMax = ary.Length - moveCnt; var i = 0; for (; i < aryMax; i++) { ary[i] = ary[i + moveCnt] >> moveBit; if (moveBit > 0 && i < aryMax - 1) ary[i] |= ary[i + moveCnt + 1] << (64 - moveBit); } for (; i < ary.Length; ++i) ary[i] = 0; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public LIB_Bitset operator >>(LIB_Bitset x, int num) { var ret = new LIB_Bitset(x.n); var moveCnt = num >> 6; var moveBit = num & 63; var aryMax = ret.ary.Length - moveCnt; var i = 0; for (; i < aryMax; i++) { ret.ary[i] = x.ary[i + moveCnt] >> moveBit; if (moveBit > 0 && i < aryMax - 1) ret.ary[i] |= x.ary[i + moveCnt + 1] << (64 - moveBit); } for (; i < ret.ary.Length; ++i) ret.ary[i] = 0; return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public bool operator ==(LIB_Bitset x, LIB_Bitset y) { if (x.n < y.n) { var t = x; x = y; y = t; } var i = 0; for (; i < y.ary.Length; i++) if (x.ary[i] != y.ary[i]) return false; for (; i < x.ary.Length; i++) if (x.ary[i] != 0) return false; return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public bool operator !=(LIB_Bitset x, LIB_Bitset y) => !(x == y); [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Equals(LIB_Bitset x) => x == this; [MethodImpl(MethodImplOptions.AggressiveInlining)] public override bool Equals(object x) => x == null ? false : Equals((LIB_Bitset)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override int GetHashCode() { var t = ary.Aggregate((a, x) => a ^ x); return (int)(((t >> 32) ^ t) & 0x000000007fffffff); } } class LIB_BitUtil { public static readonly ulong[] BitMask; static LIB_BitUtil() { BitMask = new ulong[64]; BitMask[0] = 1; for (var i = 1; i < 64; i++) BitMask[i] = BitMask[i - 1] << 1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public IEnumerable<long> ScanOne(long value) { for (; value > 0; value &= value - 1) yield return value & -value; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public int MSB(long value) { return 64 - (int)System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount((ulong)value); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public int LSB(long value) { return 64 - (int)System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount((ulong)(value & -value)); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public long PopCount(ulong value) { return (long)System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount(value); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public long PopCount(long value) => PopCount((ulong)value); [MethodImpl(MethodImplOptions.AggressiveInlining)] static public bool IsSet(ulong value, int idx) => (value & BitMask[idx]) != 0; [MethodImpl(MethodImplOptions.AggressiveInlining)] static public bool IsSet(long value, int idx) => IsSet((ulong)value, idx); [MethodImpl(MethodImplOptions.AggressiveInlining)] static public T[] BitZentansaku<T>(long bitlen, T e, Func<int, T, T> f) { var retlen = 1 << (int)bitlen; var ret = new T[retlen]; var idx = 0; ret[0] = e; for (var i = 1; i < retlen; ++i) { if (i == (1 << (idx + 1))) ++idx; ret[i] = f(idx, ret[i & (~(1 << idx))]); } return ret; } } }