結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-29 22:04:15 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,031 ms / 3,000 ms |
コード長 | 4,699 bytes |
コンパイル時間 | 14,717 ms |
コンパイル使用メモリ | 171,448 KB |
実行使用メモリ | 191,860 KB |
最終ジャッジ日時 | 2024-11-19 06:30:51 |
合計ジャッジ時間 | 27,428 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (101 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[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (h, w) = (c[0], c[1]);var a = NArr(h);var colors = new int[h][];for (var i = 0; i < h; ++i) colors[i] = Enumerable.Repeat(-1, w).ToArray();colors[0][0] = 1;colors[h - 1][w - 1] = 0;var ones = new PriorityQueue<Pair>(h, false);ones.Enqueue(new Pair(0, 1, a[0][1]));ones.Enqueue(new Pair(1, 0, a[1][0]));var zeros = new PriorityQueue<Pair>(h, false);zeros.Enqueue(new Pair(h - 1, w - 2, a[h - 1][w - 2]));zeros.Enqueue(new Pair(h - 2, w - 1, a[h - 2][w - 1]));var ans = 0;var mx = new int[] { 0, 0, -1, 1 };var my = new int[] { -1, 1, 0, 0 };while (true){++ans;var cur = ones.Dequeue();while (colors[cur.X][cur.Y] >= 0) cur = ones.Dequeue();colors[cur.X][cur.Y] = 1;var flg = true;for (var i = 0; i < 4; ++i){var nx = cur.X + mx[i];var ny = cur.Y + my[i];if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;if (colors[nx][ny] == 0){flg = false;break;}if (colors[nx][ny] < 0) ones.Enqueue(new Pair(nx, ny, a[nx][ny]));}if (!flg) break;++ans;cur = zeros.Dequeue();while (colors[cur.X][cur.Y] >= 0) cur = zeros.Dequeue();colors[cur.X][cur.Y] = 0;flg = true;for (var i = 0; i < 4; ++i){var nx = cur.X + mx[i];var ny = cur.Y + my[i];if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;if (colors[nx][ny] == 1){flg = false;break;}if (colors[nx][ny] < 0) zeros.Enqueue(new Pair(nx, ny, a[nx][ny]));}if (!flg) break;}WriteLine(ans);}class Pair : IComparable<Pair>{public int X;public int Y;public int Val;public Pair(int x, int y, int val){X = x; Y = y; Val = val;}public int CompareTo(Pair b){return Val.CompareTo(b.Val);}}class PriorityQueue<T> where T : IComparable<T>{public T[] List;public int Count;bool IsTopMax;public PriorityQueue(int count, bool isTopMax){IsTopMax = isTopMax;List = new T[Math.Max(128, count)];}public void Enqueue(T value){if (Count == List.Length){var newlist = new T[List.Length * 2];for (var i = 0; i < List.Length; ++i) newlist[i] = List[i];List = newlist;}var pos = Count;List[pos] = value;++Count;while (pos > 0){var parent = (pos - 1) / 2;if (Calc(List[parent], List[pos], true)) break;Swap(parent, pos);pos = parent;}}public T Dequeue(){--Count;Swap(0, Count);var pos = 0;while (true){var child = pos * 2 + 1;if (child >= Count) break;if (child + 1 < Count && Calc(List[child + 1], List[child], false)) ++child;if (Calc(List[pos], List[child], true)) break;Swap(pos, child);pos = child;}return List[Count];}bool Calc(T a, T b, bool equalVal){var ret = a.CompareTo(b);if (ret == 0 && equalVal) return true;return IsTopMax ? ret > 0 : ret < 0;}void Swap(int a, int b){var tmp = List[a];List[a] = List[b];List[b] = tmp;}}}