結果
問題 | No.5006 Hidden Maze |
ユーザー | g4np0n |
提出日時 | 2022-06-12 17:29:46 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 18,284 bytes |
コンパイル時間 | 6,531 ms |
実行使用メモリ | 54,920 KB |
スコア | 76,097 |
平均クエリ数 | 240.03 |
最終ジャッジ日時 | 2022-06-12 17:30:09 |
合計ジャッジ時間 | 22,653 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 87 ms
47,376 KB |
testcase_01 | AC | 106 ms
48,428 KB |
testcase_02 | AC | 77 ms
47,124 KB |
testcase_03 | AC | 80 ms
46,776 KB |
testcase_04 | AC | 92 ms
48,528 KB |
testcase_05 | AC | 114 ms
49,656 KB |
testcase_06 | AC | 85 ms
47,548 KB |
testcase_07 | AC | 81 ms
47,652 KB |
testcase_08 | AC | 180 ms
54,540 KB |
testcase_09 | AC | 148 ms
51,488 KB |
testcase_10 | AC | 79 ms
47,656 KB |
testcase_11 | AC | 84 ms
47,384 KB |
testcase_12 | AC | 95 ms
47,740 KB |
testcase_13 | AC | 90 ms
47,540 KB |
testcase_14 | AC | 99 ms
48,556 KB |
testcase_15 | AC | 86 ms
47,192 KB |
testcase_16 | AC | 83 ms
47,536 KB |
testcase_17 | AC | 99 ms
48,176 KB |
testcase_18 | AC | 103 ms
49,096 KB |
testcase_19 | AC | 84 ms
46,556 KB |
testcase_20 | AC | 78 ms
47,384 KB |
testcase_21 | AC | 80 ms
47,392 KB |
testcase_22 | AC | 82 ms
47,404 KB |
testcase_23 | AC | 87 ms
47,612 KB |
testcase_24 | AC | 107 ms
49,600 KB |
testcase_25 | AC | 93 ms
48,020 KB |
testcase_26 | AC | 189 ms
54,404 KB |
testcase_27 | AC | 96 ms
48,448 KB |
testcase_28 | AC | 94 ms
48,376 KB |
testcase_29 | AC | 184 ms
54,732 KB |
testcase_30 | AC | 81 ms
46,752 KB |
testcase_31 | AC | 82 ms
47,252 KB |
testcase_32 | AC | 101 ms
48,544 KB |
testcase_33 | AC | 90 ms
47,892 KB |
testcase_34 | AC | 81 ms
47,472 KB |
testcase_35 | AC | 80 ms
46,976 KB |
testcase_36 | AC | 107 ms
48,724 KB |
testcase_37 | AC | 192 ms
54,632 KB |
testcase_38 | AC | 120 ms
49,884 KB |
testcase_39 | AC | 89 ms
48,244 KB |
testcase_40 | AC | 84 ms
47,556 KB |
testcase_41 | AC | 88 ms
47,996 KB |
testcase_42 | AC | 83 ms
46,904 KB |
testcase_43 | AC | 88 ms
47,928 KB |
testcase_44 | AC | 82 ms
47,400 KB |
testcase_45 | AC | 91 ms
47,692 KB |
testcase_46 | AC | 169 ms
53,180 KB |
testcase_47 | AC | 90 ms
47,724 KB |
testcase_48 | AC | 117 ms
48,832 KB |
testcase_49 | AC | 188 ms
54,496 KB |
testcase_50 | AC | 87 ms
46,700 KB |
testcase_51 | AC | 91 ms
47,672 KB |
testcase_52 | AC | 88 ms
47,036 KB |
testcase_53 | AC | 104 ms
48,544 KB |
testcase_54 | AC | 124 ms
48,116 KB |
testcase_55 | AC | 101 ms
48,040 KB |
testcase_56 | AC | 80 ms
47,104 KB |
testcase_57 | AC | 100 ms
47,900 KB |
testcase_58 | AC | 108 ms
49,012 KB |
testcase_59 | AC | 80 ms
47,536 KB |
testcase_60 | AC | 84 ms
47,636 KB |
testcase_61 | AC | 89 ms
47,520 KB |
testcase_62 | AC | 98 ms
48,308 KB |
testcase_63 | AC | 85 ms
47,940 KB |
testcase_64 | AC | 106 ms
49,564 KB |
testcase_65 | AC | 97 ms
48,336 KB |
testcase_66 | AC | 91 ms
47,792 KB |
testcase_67 | AC | 128 ms
50,856 KB |
testcase_68 | AC | 137 ms
51,332 KB |
testcase_69 | AC | 166 ms
54,008 KB |
testcase_70 | AC | 79 ms
46,808 KB |
testcase_71 | AC | 79 ms
46,620 KB |
testcase_72 | AC | 91 ms
47,112 KB |
testcase_73 | AC | 88 ms
47,716 KB |
testcase_74 | AC | 83 ms
47,048 KB |
testcase_75 | AC | 84 ms
47,440 KB |
testcase_76 | AC | 81 ms
46,852 KB |
testcase_77 | AC | 138 ms
50,896 KB |
testcase_78 | AC | 117 ms
49,824 KB |
testcase_79 | AC | 186 ms
54,920 KB |
testcase_80 | AC | 80 ms
46,596 KB |
testcase_81 | AC | 82 ms
47,820 KB |
testcase_82 | AC | 83 ms
47,796 KB |
testcase_83 | AC | 78 ms
46,960 KB |
testcase_84 | AC | 117 ms
49,916 KB |
testcase_85 | AC | 97 ms
48,172 KB |
testcase_86 | AC | 82 ms
47,140 KB |
testcase_87 | AC | 98 ms
48,596 KB |
testcase_88 | AC | 126 ms
49,892 KB |
testcase_89 | AC | 126 ms
49,916 KB |
testcase_90 | AC | 91 ms
47,712 KB |
testcase_91 | AC | 84 ms
47,084 KB |
testcase_92 | AC | 99 ms
50,516 KB |
testcase_93 | AC | 79 ms
47,156 KB |
testcase_94 | AC | 103 ms
49,412 KB |
testcase_95 | AC | 111 ms
49,492 KB |
testcase_96 | AC | 90 ms
47,540 KB |
testcase_97 | AC | 159 ms
53,352 KB |
testcase_98 | AC | 175 ms
54,184 KB |
testcase_99 | AC | 134 ms
50,820 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 105 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 をご覧ください /home/judge/data/code/Main.cs(16,10): warning CS0414: フィールド 'Program.mod' が割り当てられていますが、値は使用されていません [/home/judge/data/code/main.csproj] 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 System.Runtime.CompilerServices; using System.Numerics; using System.Threading; using System.Diagnostics; using static System.Math; partial class Program { static int[] dx = new int[] { 1, 0, -1, 0, 1, -1, -1, 1 }; static int[] dy = new int[] { 0, 1, 0, -1, 1, 1, -1, -1 }; //long mod = 1000000007; long mod = 998244353; public void Solve() { var (H, W, P) = io.GetMulti<int, int, double>(); var s = 0; var t = H * W - 1; var N = H * W; long INF = 1000000000; int[] dv = new int[] { 1, W, -1, -W }; var path = new long[2][]; var unclearCost = 11; var clearCost = 10; for (int i = 0; i < 2; i++) { path[i] = new long[N]; path[i].AsSpan().Fill(unclearCost); } for (int i = 0; i < N; i++) { if (i % W == N - 1) path[0][i] = INF; if (i / W == N - 1) path[1][i] = INF; } var clear = new bool[2][]; for (int i = 0; i < 2; i++) clear[i] = new bool[N]; while (true) { var pq = new PriorityQueue<int>(); var dist = new long[N]; dist.AsSpan().Fill(INF); var from = new int[N]; from.AsSpan().Fill(-1); dist[s] = 0; pq.Enqueue(0, s); while (pq.Count > 0) { var (d, v) = pq.Dequeue(); if (v == t) break; if (dist[v] != d) continue; for (int i = 0; i < 4; i++) { var ny = v / W + dy[i]; var nx = v % W + dx[i]; if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue; var to = v + dv[i]; var td = i < 2 ? path[i][v] : path[i - 2][to]; var alt = d + td; if (alt >= dist[to]) continue; dist[to] = alt; from[to] = v; pq.Enqueue(alt, to); } } var st = new List<int>(); var tt = t; while (from[tt] != -1) { st.Add(tt); tt = from[tt]; } st.Add(0); st.Reverse(); var output = new char[st.Count - 1]; for (int i = 0; i < st.Count - 1; i++) { var dd = st[i + 1] - st[i]; output[i] = dd == 1 ? 'R' : dd == W ? 'D' : dd == -1 ? 'L' : 'U'; } Console.WriteLine(output); var x = io.GetInt(); if (x == -1) { return; } for (int i = 0; i < x; i++) { var xx = st[i]; var yy = st[i + 1]; if (yy < xx) (yy, xx) = (xx, yy); var v = yy - xx == 1 ? 0 : 1; clear[v][xx] = true; path[v][xx] = clearCost; } var eb = st[x]; var ea = st[x + 1]; if (ea < eb) (ea, eb) = (eb, ea); var ev = ea - eb == 1 ? 0 : 1; var pena = (long)(100 / P * path[ev][eb]); if (!clear[ev][eb]) { path[ev][eb] *= pena; } } } class PriorityQueue<T> { /// <summary> /// 空の優先度付きキューを生成します。 /// </summary> public PriorityQueue() { _keys = new List<long>(); _elements = new List<T>(); } List<long> _keys; List<T> _elements; /// <summary> /// 優先度付きキューに要素を追加します。 /// 計算量は O(log(要素数)) です。 /// </summary> public void Enqueue(long key, T elem) { var n = _elements.Count; _keys.Add(key); _elements.Add(elem); while (n != 0) { var i = (n - 1) / 2; if (_keys[n] < _keys[i]) { (_keys[n], _keys[i]) = (_keys[i], _keys[n]); (_elements[n], _elements[i]) = (_elements[i], _elements[n]); } n = i; } } /// <summary> /// 頂点要素を返し、削除します。 /// 計算量は O(log(要素数)) です。 /// </summary> public (long, T) Dequeue() { var t = Peek; Pop(); return t; } void Pop() { var n = _elements.Count - 1; _elements[0] = _elements[n]; _elements.RemoveAt(n); _keys[0] = _keys[n]; _keys.RemoveAt(n); for (int i = 0, j; (j = 2 * i + 1) < n;) { //左の子と右の子で右の子の方が優先度が高いなら右の子を処理したい if ((j != n - 1) && _keys[j] > _keys[j + 1]) j++; //親より子が優先度が高いなら親子を入れ替える if (_keys[i] > _keys[j]) { (_keys[i], _keys[j]) = (_keys[j], _keys[i]); (_elements[i], _elements[j]) = (_elements[j], _elements[i]); } i = j; } } /// <summary> /// 頂点要素を返します。 /// 計算量は O(1) です。 /// </summary> public (long, T) Peek => (_keys[0], _elements[0]); /// <summary> /// 優先度付きキューに格納されている要素の数を返します。 /// 計算量は O(1) です。 /// </summary> public int Count => _elements.Count; } IO io = new IO(); static void Main() { Console.SetIn(new StreamReader(Console.OpenStandardInput(8192))); //Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var program = new Program(); //var t = new Thread(program.Solve, 134217728); //t.Start(); //t.Join(); program.Solve(); Console.Out.Flush(); Console.Read(); } } //------------------------------------------------------------------------------------------------------------------ public static class Ex { public static bool IsNullOrEmpty(this string s) { return string.IsNullOrEmpty(s); } public static void yesno(this bool b) => Console.WriteLine(b ? "yes" : "no"); public static void YesNo(this bool b) => Console.WriteLine(b ? "Yes" : "No"); public static void YESNO(this bool b) => Console.WriteLine(b ? "YES" : "NO"); public static void Yes() => Console.WriteLine("Yes"); public static void YES() => Console.WriteLine("YES"); public static void No() => Console.WriteLine("No"); public static void NO() => Console.WriteLine("NO"); public static void M1() => Console.WriteLine("-1"); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax(ref this int a, int b) { if (a < b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin(ref this int a, int b) { if (a > b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax(ref this long a, long b) { if (a < b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin<T>(ref this long a, long b) { if (a > b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax<T>(ref this T a, T b) where T : struct, IComparable<T> { if (b.CompareTo(a) > 0) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin<T>(ref this T a, T b) where T : struct, IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } else return false; } /// <summary> /// constraintを満たす最小のインデックスを返します。 /// </summary> /// <param name="constraint">T key が満たすべき制約</param> /// <returns>制約を満たす最小のインデックス(0-indexed)</returns> public static int LowerBound<T>(this IList<T> ls, Func<T, bool> constraint) { var ng = -1; var ok = ls.Count; while (ok - ng > 1) { var mid = (ok + ng) / 2; if (constraint(ls[mid])) ok = mid; else ng = mid; } return ok; } public static void Swap(this IList<int> arr, int a, int b) => (arr[a], arr[b]) = (arr[b], arr[a]); public static long[] GetCum(this IList<long> ls) { var res = new long[ls.Count + 1]; for (int i = 0; i < ls.Count; i++) res[i + 1] = res[i] + ls[i]; return res; } public static T[] GetCum<T>(this IList<T> ls, bool fromLeft, T gen, Func<T, T, T> func) { var res = new T[ls.Count + 1]; res.AsSpan().Fill(gen); if (fromLeft) { for (int i = 0; i < ls.Count; i++) res[i + 1] = func(res[i], ls[i]); } else { for (int i = ls.Count; i > 0; i--) res[i - 1] = func(res[i], ls[i - 1]); } return res; } public static string[] StringListFastSort(this IList<string> ls) { var res = ls.ToArray(); Array.Sort(res, StringComparer.OrdinalIgnoreCase); return res; } public static int PopCount(this uint bits) { bits = bits - ((bits >> 1) & 0x55555555); bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333); return (int)(((bits + (bits >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); } public static T[] Repeat<T>(this T element, int N) { var res = new T[N]; res.AsSpan().Fill(element); return res; } public static T[][] Repeat<T>(this T element, int H, int W) { var res = new T[H][]; for (int i = 0; i < H; i++) { res[i] = new T[W]; res[i].AsSpan().Fill(element); } return res; } public static T[][][] Repeat<T>(this T element, int H, int W, int R) { var res = new T[H][][]; for (int i = 0; i < H; i++) { res[i] = new T[W][]; for (int j = 0; j < W; j++) { res[i][j] = new T[R]; res[i][j].AsSpan().Fill(element); } } return res; } } class IO { public string GetStr() => Console.ReadLine().Trim(); public char GetChar() => Console.ReadLine().Trim()[0]; public int GetInt() => int.Parse(Console.ReadLine().Trim()); public long GetLong() => long.Parse(Console.ReadLine().Trim()); public double GetDouble() => double.Parse(Console.ReadLine().Trim()); public decimal GetDecimal() => decimal.Parse(Console.ReadLine().Trim()); public string[] GetStrArray() => Console.ReadLine().Trim().Split(' '); public string[][] GetStrArray(int N) { var res = new string[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' '); return res; } public int[] GetIntArray() => Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); public int[][] GetIntArray(int N) { var res = new int[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); return res; } public long[] GetLongArray() => Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray(); public long[][] GetLongArray(int N) { var res = new long[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray(); return res; } public decimal[] GetDecimalArray() => Console.ReadLine().Trim().Split(' ').Select(decimal.Parse).ToArray(); public decimal[][] GetDecimalArray(int N) { var res = new decimal[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(decimal.Parse).ToArray(); return res; } public char[] GetCharArray() => Console.ReadLine().Trim().Split(' ').Select(char.Parse).ToArray(); public double[] GetDoubleArray() => Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray(); public double[][] GetDoubleArray(int N) { var res = new double[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray(); return res; } public char[][] GetGrid(int H) { var res = new char[H][]; for (int i = 0; i < H; i++) res[i] = Console.ReadLine().Trim().ToCharArray(); return res; } public List<int>[] GetUnweightedAdjanceyList(int V, int E, bool isDirected, bool isNode_0indexed) { var ls = new List<int>[V]; for (int i = 0; i < V; i++) ls[i] = new List<int>(); for (int i = 0; i < E; i++) { var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); if (isNode_0indexed == false) { input[0]--; input[1]--; } ls[input[0]].Add(input[1]); if (isDirected == false) ls[input[1]].Add(input[0]); } return ls; } public List<(int to, long dist)>[] GetWeightedAdjacencyList(int V, int E, bool isDirected, bool isNode_0indexed) { var ls = new List<(int to, long dist)>[V]; for (int i = 0; i < V; i++) ls[i] = new List<(int to, long dist)>(); for (int i = 0; i < E; i++) { var hoge = Console.ReadLine().Split(' '); var a = int.Parse(hoge[0]); var b = int.Parse(hoge[1]); var c = long.Parse(hoge[2]); if (isNode_0indexed == false) { a--; b--; } ls[a].Add((b, c)); if (isDirected == false) ls[b].Add((a, c)); } return ls; } [MethodImpl(MethodImplOptions.AggressiveInlining)] bool eq<T, U>() => typeof(T).Equals(typeof(U)); [MethodImpl(MethodImplOptions.AggressiveInlining)] T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T)); [MethodImpl(MethodImplOptions.AggressiveInlining)] T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s)) : eq<T, long>() ? ct<T, long>(long.Parse(s)) : eq<T, double>() ? ct<T, double>(double.Parse(s)) : eq<T, decimal>() ? ct<T, decimal>(decimal.Parse(s)) : eq<T, char>() ? ct<T, char>(s[0]) : ct<T, string>(s); [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T>(out T a) => a = cv<T>(GetStr()); [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T, U>(out T a, out U b) { var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T, U, V>(out T a, out U b, out V c) { var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T, U, V, W>(out T a, out U b, out V c, out W d) { var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e) { var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f) { var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); f = cv<Y>(ar[5]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U) GetMulti<T, U>() { var ar = Console.ReadLine().Split(' '); return (cv<T>(ar[0]), cv<U>(ar[1])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V) GetMulti<T, U, V>() { var ar = Console.ReadLine().Split(' '); return (cv<T>(ar[0]), cv<U>(ar[1]), cv<V>(ar[2])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W) GetMulti<T, U, V, W>() { var ar = Console.ReadLine().Split(' '); return (cv<T>(ar[0]), cv<U>(ar[1]), cv<V>(ar[2]), cv<W>(ar[3])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W, X) GetMulti<T, U, V, W, X>() { var ar = Console.ReadLine().Split(' '); return (cv<T>(ar[0]), cv<U>(ar[1]), cv<V>(ar[2]), cv<W>(ar[3]), cv<X>(ar[4])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W, X, Y) GetMulti<T, U, V, W, X, Y>() { var ar = Console.ReadLine().Split(' '); return (cv<T>(ar[0]), cv<U>(ar[1]), cv<V>(ar[2]), cv<W>(ar[3]), cv<X>(ar[4]), cv<Y>(ar[5])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print() => Console.WriteLine(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print<T>(T t) => Console.WriteLine(t); [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print<T>(string separator, IList<T> ls) => Console.WriteLine(string.Join(separator, ls)); public void Debug<T>(IList<T> ls) { Console.Error.WriteLine(); Console.Error.WriteLine("[" + string.Join(",", ls) + "]"); } public void Debug<T>(IList<IList<T>> ls) { Console.Error.WriteLine(); foreach (var l in ls) { Console.Error.WriteLine("[" + string.Join(",", l) + "]"); } Console.Error.WriteLine(); } }