結果
問題 | No.2673 A present from B |
ユーザー |
|
提出日時 | 2024-03-15 22:18:34 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 5,530 bytes |
コンパイル時間 | 8,704 ms |
コンパイル使用メモリ | 168,288 KB |
実行使用メモリ | 189,900 KB |
最終ジャッジ日時 | 2024-09-30 01:40:55 |
合計ジャッジ時間 | 11,576 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (85 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (n, m) = (c[0], c[1]);var a = NList;var cnt = n * (m + 1);var tree = new List<(int to, int len)>[cnt];for (var i = 0; i < tree.Length; ++i) tree[i] = new List<(int to, int len)>();for (var i = 0; i <= m; ++i) for (var j = 0; j < n; ++j){if (j + 1 < n){tree[i * n + j].Add((i * n + j + 1, 1));tree[i * n + j + 1].Add((i * n + j, 1));}if (i < m){if (a[i] - 1 == j){tree[(i + 1) * n + j].Add((i * n + j + 1, 0));}else if (a[i] % n == j){tree[(i + 1) * n + j].Add((i * n + j - 1, 0));}else{tree[(i + 1) * n + j].Add((i * n + j, 0));}}}var INF = int.MaxValue / 2;var len = Enumerable.Repeat(INF, cnt).ToArray();len[m * n] = 0;var q = new Deque<(int pos, int len)>(cnt);q.PushFront((m * n, 0));while (q.Count > 0){var cur = q.PopFront();foreach (var next in tree[cur.pos]){if (len[next.to] <= cur.len + next.len) continue;len[next.to] = cur.len + next.len;if (next.len == 0) q.PushFront((next.to, len[next.to]));else q.PushBack((next.to, len[next.to]));}}WriteLine(string.Join(" ", len.Skip(1).Take(n - 1)));}/// 前後から出し入れ可能なキューclass Deque<T>{int _s = 0;int _t = 0;T[] _arr;public Deque() : this(4){}public Deque(int size){_arr = new T[size];}public Deque(IEnumerable<T> init){var list = init.ToArray();var size = 4;while (size <= list.Length) size <<= 1;_arr = new T[size];for (var i = 0; i < list.Length; ++i) _arr[i] = list[i];_t = _arr.Length;}public int Count{get { return (_t + _arr.Length - _s) % _arr.Length; }}/// <summary>キューの末尾に追加する</summary>/// <param name="item">追加するアイテム</param>public void PushBack(T item){if (Count + 1 == _arr.Length) Expand();if (_t == _arr.Length) _t = 0;_arr[_t++] = item;}/// <summary>キューの先頭からアイテムを取り出す</summary>/// <returns>取り出したアイテム</returns>public T PopFront(){var ret = _arr[_s++];if (_s == _arr.Length) _s = 0;return ret;}/// <summary>キューの先頭に追加する</summary>/// <param name="item">追加するアイテム</param>public void PushFront(T item){if (Count + 1 == _arr.Length) Expand();if (_s == 0) _s = _arr.Length;_arr[--_s] = item;}/// <summary>キューの末尾からアイテムを取り出す</summary>/// <returns>取り出したアイテム</returns>public T PopBack(){var ret = _arr[--_t];if (_t == 0) _t = _arr.Length;return ret;}/// <summary>キューの先頭にあるアイテムを取得する</summary>/// <returns>キューの先頭にあるアイテム</returns>/// <exception cref="InvalidOperationException">キューが空の場合</exception>public T Peek(){if (Count == 0) throw new InvalidOperationException("deque is empty");return _arr[_s];}/// <summary>キューの末尾にあるアイテムを取得する</summary>/// <returns>キューの末尾にあるアイテム</returns>/// <exception cref="InvalidOperationException">キューが空の場合</exception>public T PeekBack(){if (Count == 0) throw new InvalidOperationException("deque is empty");return _arr[_t - 1];}void Expand(){var count = Count;var na = new T[_arr.Length * 2];var cur = 0;if (_s <= _t){for (var i = _s; i < _t; ++i) na[cur++] = _arr[i];}else{for (var i = _s; i < _arr.Length; ++i) na[cur++] = _arr[i];for (var i = 0; i < _t; ++i) na[cur++] = _arr[i];}_s = 0;_t = count;_arr = na;}}}