結果
| 問題 |
No.2946 Puyo
|
| ユーザー |
 fairy_lettuce
|
| 提出日時 | 2025-08-25 03:49:31 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 102 ms / 2,000 ms |
| コード長 | 29,413 bytes |
| コンパイル時間 | 8,053 ms |
| コンパイル使用メモリ | 169,000 KB |
| 実行使用メモリ | 199,352 KB |
| 最終ジャッジ日時 | 2025-08-25 03:49:45 |
| 合計ジャッジ時間 | 14,293 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (143 ミリ秒)。 /home/judge/data/code/Main.cs(59,4524): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using CpLibrary.Mathematics;
using CpLibrary.Util;
using System.Buffers;
using System.Buffers.Text;
using System.Collections;
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using static CpLibrary.StaticItems;
namespace CpLibrary.Contest
{
public class SolverH : SolverBase
{
static void Main() => new SolverH().RunOnline();
public override void Solve()
{
var (h, w) = sr.ReadValue<int, int>();
var g = sr.ReadStringArray(h);
var uf = new CpLibrary.Graph.UnionFind(h * w);
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (i > 0 && g[i][j] == g[i - 1][j]) uf.Unite(i * w + j, (i - 1) * w + j);
if (j > 0 && g[i][j] == g[i][j - 1]) uf.Unite(i * w + j, i * w + j - 1);
}
}
var ans = CreateArray(h, w, (i, j) => g[i][j]);
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (uf.Size(i * w + j) >= 4) ans[i][j] = '.';
}
}
for (int i = 0; i < h; i++)
{
sw.WriteLine(ans[i].Join());
}
}
public override void Init()
{
/*
* Write your init code here!
*/
}
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace CpLibrary { public interface ISolver { public void Run(StreamReader sr, StreamWriter sw); } }
namespace CpLibrary { public abstract class SolverBase : ISolver { public bool StartsOnThread { get; set; } = false; public int Testcases { get; set; } = 1; public Scanner sr; public StreamWriter sw; public abstract void Init(); public abstract void Solve(); public void Run(StreamReader reader, StreamWriter writer) { this.sw = writer; sr = new Scanner(reader); Console.SetOut(writer); if (StartsOnThread) { var thread = new Thread(new ThreadStart(RunInternal), 1 << 27); thread.Start(); thread.Join(); } else { RunInternal(); } } void RunInternal() { Init(); var testcases = Testcases; while (testcases-- > 0) { Solve(); } } protected void RunOnline() { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; var sr = new StreamReader(Console.OpenStandardInput()); Run(sr, sw); Console.Out.Flush(); } } }
namespace CpLibrary { public static class Extension { public static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); public static string Join<T>(this IEnumerable<T> x, char separator) => string.Join(separator, x); public static int UpperBound<T>(this IList<T> list, T value) => list.BinarySearch(value, true, 0, list.Count, Comparer<T>.Default); public static int LowerBound<T>(this IList<T> list, T value) => list.BinarySearch(value, false, 0, list.Count, Comparer<T>.Default); public static int BinarySearch<T>(this IList<T> list, T value, bool isUpperBound, int index, int length, Comparer<T> comparer) { var low = index - 1; var high = index + length; while (high - low > 1) { var mid = low + (high - low) / 2; var res = comparer.Compare(list[mid], value); if (res < 0 || (isUpperBound && res == 0)) low = mid; else high = mid; } return high; } public static bool Chmax<T>(ref this T a, T b) where T : struct, IComparable<T> { if (a.CompareTo(b) >= 0) return false; a = b; return true; } public static bool Chmin<T>(ref this T a, T b) where T : struct, IComparable<T> { if (a.CompareTo(b) <= 0) return false; a = b; return true; } } }
namespace CpLibrary.Graph { public static partial class Graph { public interface IEdge { int To { get; } } public interface IWeightedEdge<T> : IEdge where T : INumber<T> { T Weight { get; } } public interface IGraph<TEdge> where TEdge : IEdge { public List<TEdge> this[int index] { get; } public int NodeCount { get; } public List<TEdge> Next(int x); } public interface IWeightedGraph<TEdge, TWeight> : IGraph<TEdge> where TWeight : INumber<TWeight> where TEdge : IWeightedEdge<TWeight> { } public struct BasicEdge : IEdge { public int To { get; private set; } public BasicEdge(int to) { this.To = to; } public override string ToString() => $"{To}"; public static implicit operator BasicEdge(int edge) => new BasicEdge(edge); public static implicit operator int (BasicEdge edge) => edge.To; } public struct WeightedEdge<T> : IWeightedEdge<T> where T : INumber<T> { public int To { get; private set; } public T Weight { get; private set; } public WeightedEdge(int to, T weight) { To = to; Weight = weight; } public WeightedEdge(int to) : this(to, default(T)) { } public override string ToString() => $"[{Weight}] -> {To}"; public void Deconstruct(out int to, out T weight) => (to, weight) = (To, Weight); } public class UndirectedGraph : IGraph<BasicEdge> { public readonly List<List<BasicEdge>> g; public List<BasicEdge> this[int index] => g[index]; public int NodeCount => g.Count; public UndirectedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<BasicEdge>()).ToList(); public UndirectedGraph(int nodeCount, int[] u, int[] v) : this(nodeCount) { if (u.Length != v.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(v)} must have the same length."); for (var i = 0; i < u.Length; i++) { AddEdge(u[i], v[i]); } } public void AddEdge(int u, int v) { g[u].Add(v); g[v].Add(u); } public void AddNode() => g.Add(new List<BasicEdge>()); public List<BasicEdge> Next(int x) => g[x]; } public class DirectedGraph : IGraph<BasicEdge> { public readonly List<List<BasicEdge>> g; public List<BasicEdge> this[int index] => g[index]; public int NodeCount => g.Count; public DirectedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<BasicEdge>()).ToList(); public DirectedGraph(int nodeCount, int[] from, int[] to) : this(nodeCount) { if (from.Length != to.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(to)} must have the same length."); for (var i = 0; i < from.Length; i++) { AddEdge(from[i], to[i]); } } public void AddEdge(int from, int to) => g[from].Add(to); public void AddNode() => g.Add(new List<BasicEdge>()); public List<BasicEdge> Next(int x) => g[x]; } public class UndirectedWeightedGraph<T> : IWeightedGraph<WeightedEdge<T>, T> where T : INumber<T> { public readonly List<List<WeightedEdge<T>>> g; public List<WeightedEdge<T>> this[int index] => g[index]; public int NodeCount => g.Count; public UndirectedWeightedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<WeightedEdge<T>>()).ToList(); public UndirectedWeightedGraph(int nodeCount, int[] u, int[] v, T[] weight) : this(nodeCount) { if (u.Length != v.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(v)} must have the same length."); if (u.Length != weight.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(weight)} must have the same length."); if (weight.Length != v.Length) throw new ArgumentException($"The arrays {nameof(v)} and {nameof(weight)} must have the same length."); for (var i = 0; i < u.Length; i++) { AddEdge(u[i], v[i], weight[i]); } } public void AddEdge(int u, int v, T w) { g[u].Add(new WeightedEdge<T>(v, w)); g[v].Add(new WeightedEdge<T>(u, w)); } public void AddNode() => g.Add(new List<WeightedEdge<T>>()); public List<WeightedEdge<T>> Next(int x) => g[x]; } public class DirectedWeightedGraph<T> : IWeightedGraph<WeightedEdge<T>, T> where T : INumber<T> { public readonly List<List<WeightedEdge<T>>> g; public List<WeightedEdge<T>> this[int index] => g[index]; public int NodeCount => g.Count; public DirectedWeightedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<WeightedEdge<T>>()).ToList(); public DirectedWeightedGraph(int nodeCount, int[] from, int[] to, T[] weight) : this(nodeCount) { if (from.Length != to.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(to)} must have the same length."); if (from.Length != weight.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(weight)} must have the same length."); if (weight.Length != to.Length) throw new ArgumentException($"The arrays {nameof(to)} and {nameof(weight)} must have the same length."); for (var i = 0; i < from.Length; i++) { AddEdge(from[i], to[i], weight[i]); } } public void AddEdge(int from, int to, T w) { g[from].Add(new WeightedEdge<T>(to, w)); } public void AddNode() => g.Add(new List<WeightedEdge<T>>()); public List<WeightedEdge<T>> Next(int x) => g[x]; } } }
namespace CpLibrary.Graph { public class UnionFind { public int Count { get; private set; } int[] parent; int[] rank; int[] size; public UnionFind(int n) { parent = Enumerable.Range(0, n).ToArray(); rank = Enumerable.Repeat(0, n).ToArray(); size = Enumerable.Repeat(1, n).ToArray(); } public void Unite(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; if (rank[x] > rank[y]) { parent[y] = x; size[x] += size[y]; } else { parent[x] = y; if (rank[x] == rank[y]) rank[x]++; size[y] += size[x]; } } public int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); } public bool IsSame(int x, int y) => Find(x) == Find(y); public int Size(int x) => size[Find(x)]; } }
namespace CpLibrary { public class Scanner { public Stream stream { get; private set; } byte[] buffer; int length; int index; readonly static byte[] DEFAULT_SEPARATORS = { (byte)'\n', (byte)'\r', (byte)'\t', (byte)' ' }; byte[] separators; public Scanner(Stream stream, byte[] separators, int size = 1 << 12) { this.stream = stream; this.separators = separators; buffer = GC.AllocateUninitializedArray<byte>(size); length = index = 0; } public Scanner(Stream stream, int size = 1 << 12) : this(stream, DEFAULT_SEPARATORS, size) { } public Scanner(int size = 1 << 12) : this(Console.OpenStandardInput(), DEFAULT_SEPARATORS, size) { } public Scanner(StreamReader sr, byte[] separators, int size = 1 << 12) : this(sr.BaseStream, separators, size) { } public Scanner(StreamReader sr, int size = 1 << 12) : this(sr.BaseStream, DEFAULT_SEPARATORS, size) { } [MethodImpl(MethodImplOptions.AggressiveInlining)] static bool IsSeparator(byte c) => c <= ' '; [MethodImpl(MethodImplOptions.AggressiveInlining)] static bool IsNewLine(byte c) => c >= '\n' && c <= '\r'; void Fill() { if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; if (length < buffer.Length) buffer[length] = (byte)'\n'; } while (IsSeparator(buffer[index])) { index++; if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; if (length < buffer.Length) buffer[length] = (byte)'\n'; } } if (index + 64u >= length && !IsSeparator(buffer[^1])) { buffer.AsSpan(index, length - index).CopyTo(buffer); length -= index; index = 0; length = stream.Read(buffer, length, buffer.Length - length) + length; if (length < buffer.Length) buffer[length] = (byte)'\n'; } } public Span<byte> ReadToken() { if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; } while (IsSeparator(buffer[index])) { index++; if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; } } var next = buffer.AsSpan(index, length - index).IndexOfAny(separators.AsSpan()); if (length < buffer.Length) { var p = index; index = (int)Math.Min((uint)(next), (uint)(length - index)) + index; return buffer.AsSpan(p, index - p); } var pool = ArrayPool<byte>.Shared.Rent(buffer.Length); var pindex = 0; while (length > 0 && (uint)next >= (uint)length) { if (pool.Length - pindex < length - index) Resize(ref pool, pool.Length); buffer.AsSpan(index).CopyTo(pool.AsSpan(pindex)); pindex += length - index; length = stream.Read(buffer, 0, buffer.Length); index = 0; next = buffer.AsSpan(index, length - index).IndexOfAny(separators); } if (next == -1) next = length; if (pool.Length - pindex < next) Resize(ref pool, pool.Length); buffer.AsSpan(index, next).CopyTo(pool.AsSpan(pindex)); pindex += next; index = next + index; try { return pool.AsSpan(0, pindex); } finally { ArrayPool<byte>.Shared.Return(pool); } } void Resize<T>(ref T[] arr, int l) { var p = arr; arr = ArrayPool<T>.Shared.Rent(l << 1); p.AsSpan().CopyTo(arr); ArrayPool<T>.Shared.Return(p); } public string Read() => Encoding.UTF8.GetString(ReadToken()); public string ReadString() => Read(); public string[] ReadStringArray(int n) { var arr = GC.AllocateUninitializedArray<string>(n); for (int i = 0; i < n; i++) { arr[i] = ReadString(); } return arr; } public uint ReadUInt() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out uint value, out int bc); index += bc; return value; } public int ReadInt() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out int value, out int bc); index += bc; return value; } public ulong ReadULong() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out ulong value, out int bc); index += bc; return value; } public long ReadLong() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out long value, out int bc); index += bc; return value; } public double ReadDouble() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out double value, out int bc); index += bc; return value; } public decimal ReadDecimal() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out decimal value, out int bc); index += bc; return value; } public int[] ReadIntArray(int n) => ReadValueArray<int>(n); public uint[] ReadUIntArray(int n) => ReadValueArray<uint>(n); public ulong[] ReadULongArray(int n) => ReadValueArray<ulong>(n); public long[] ReadLongArray(int n) => ReadValueArray<long>(n); public double[] ReadDoubleArray(int n) => ReadValueArray<double>(n); public decimal[] ReadDecimalArray(int n) => ReadValueArray<decimal>(n); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T ReadValue<T>() { if (typeof(T) == typeof(int)) return (T)(object)ReadInt(); if (typeof(T) == typeof(uint)) return (T)(object)ReadUInt(); if (typeof(T) == typeof(long)) return (T)(object)ReadLong(); if (typeof(T) == typeof(ulong)) return (T)(object)ReadULong(); if (typeof(T) == typeof(double)) return (T)(object)ReadDouble(); if (typeof(T) == typeof(decimal)) return (T)(object)ReadDecimal(); if (typeof(T) == typeof(string)) return (T)(object)ReadString(); throw new NotSupportedException(); } public (T1, T2) ReadValue<T1, T2>() => (ReadValue<T1>(), ReadValue<T2>()); public (T1, T2, T3) ReadValue<T1, T2, T3>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>()); public (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>()); public (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>()); public (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>()); public (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>(), ReadValue<T7>()); public T1[] ReadValueArray<T1>(int n) { var arr = GC.AllocateUninitializedArray<T1>(n); for (int i = 0; i < n; i++) { arr[i] = ReadValue<T1>(); } return arr; } public (T1[], T2[]) ReadValueArray<T1, T2>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i]) = ReadValue<T1, T2>(); } return (a1, a2); } public (T1[], T2[], T3[]) ReadValueArray<T1, T2, T3>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i]) = ReadValue<T1, T2, T3>(); } return (a1, a2, a3); } public (T1[], T2[], T3[], T4[]) ReadValueArray<T1, T2, T3, T4>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i]) = ReadValue<T1, T2, T3, T4>(); } return (a1, a2, a3, a4); } public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray<T1, T2, T3, T4, T5>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i]) = ReadValue<T1, T2, T3, T4, T5>(); } return (a1, a2, a3, a4, a5); } public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray<T1, T2, T3, T4, T5, T6>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); var a6 = GC.AllocateUninitializedArray<T6>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i], a6[i]) = ReadValue<T1, T2, T3, T4, T5, T6>(); } return (a1, a2, a3, a4, a5, a6); } public (T1[], T2[], T3[], T4[], T5[], T6[], T7[]) ReadValueArray<T1, T2, T3, T4, T5, T6, T7>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); var a6 = GC.AllocateUninitializedArray<T6>(n); var a7 = GC.AllocateUninitializedArray<T7>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i], a6[i], a7[i]) = ReadValue<T1, T2, T3, T4, T5, T6, T7>(); } return (a1, a2, a3, a4, a5, a6, a7); } public (T1, T2)[] ReadTupleArray<T1, T2>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2>(); } return ret; } public (T1, T2, T3)[] ReadTupleArray<T1, T2, T3>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3>(); } return ret; } public (T1, T2, T3, T4)[] ReadTupleArray<T1, T2, T3, T4>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4>(); } return ret; } public (T1, T2, T3, T4, T5)[] ReadTupleArray<T1, T2, T3, T4, T5>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5>(); } return ret; } public (T1, T2, T3, T4, T5, T6)[] ReadTupleArray<T1, T2, T3, T4, T5, T6>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5, T6)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5, T6>(); } return ret; } public (T1, T2, T3, T4, T5, T6, T7)[] ReadTupleArray<T1, T2, T3, T4, T5, T6, T7>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5, T6, T7)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5, T6, T7>(); } return ret; } } }
namespace CpLibrary.Mathematics { [DebuggerDisplay("{ToString(), nq}")] public class Matrix<T> : IEquatable<Matrix<T>>, IEnumerable<T>, IEnumerable<IEnumerable<T>> where T : INumberBase<T> { int row; int column; public T[] value; public Matrix(int r, int c) : this(r, c, new T[r * c]) { } public Matrix(int r, int c, IEnumerable<T> a) { value = a.ToArray(); row = r; column = c; } public Matrix(int r, int c, T[] a) { value = a; row = r; column = c; } public Matrix(T[][] a) { if (a is null || a.Length == 0) throw new ArgumentException("Input array cannot be null or empty.", nameof(a)); row = a.Length; column = a[0].Length; if (!a.Select(b => b.Length).All(x => x == column)) throw new ArgumentException("All rows must have the same length.", nameof(a)); value = a.SelectMany(x => x).ToArray(); } public Matrix(T[, ] a) { if (a is null || a.Length == 0) throw new ArgumentException("Input array cannot be null or empty.", nameof(a)); row = a.GetLength(0); column = a.GetLength(1); value = a.Cast<T>().ToArray(); } public Span<T> this[int r] {[MethodImpl(MethodImplOptions.AggressiveInlining)] get => value.AsSpan(r * column, column); } public T this[int r, int c] {[MethodImpl(MethodImplOptions.AggressiveInlining)] get => value[r * column + c]; [MethodImpl(MethodImplOptions.AggressiveInlining)] set => this.value[r * column + c] = value; } public T[][] Rows => ToRowArray(); public static Matrix<T> operator +(Matrix<T> lhs, Matrix<T> rhs) { if (lhs.row != rhs.row) throw new ArgumentException(); if (lhs.column != rhs.column) throw new ArgumentException(); var ret = new T[lhs.row * lhs.column]; for (int i = 0; i < lhs.row * lhs.column; i++) { ret[i] = lhs.value[i] + rhs.value[i]; } return new Matrix<T>(lhs.row, lhs.column, ret); } public static Matrix<T> operator -(Matrix<T> lhs, Matrix<T> rhs) { if (lhs.row != rhs.row) throw new ArgumentException(); if (lhs.column != rhs.column) throw new ArgumentException(); var ret = new T[lhs.row * lhs.column]; for (int i = 0; i < lhs.row * lhs.column; i++) { ret[i] = lhs.value[i] - rhs.value[i]; } return new Matrix<T>(lhs.row, lhs.column, ret); } public static Matrix<T> operator *(T k, Matrix<T> x) { var ret = new T[x.row * x.column]; for (int i = 0; i < x.row * x.column; i++) { ret[i] = k * x.value[i]; } return new Matrix<T>(x.row, x.column, ret); } public static Matrix<T> operator *(Matrix<T> x, T k) => k * x; public static Matrix<T> operator *(Matrix<T> l, Matrix<T> r) { if (l.column != r.row) throw new ArgumentException(); var rt = r.Transpose(); var lv = l.value; var rtv = rt.value; var ret = new T[l.row * r.column]; for (int i = 0; i < l.row; i++) { for (int j = 0; j < r.column; j++) { var sum = T.Zero; for (int k = 0; k < l.column; k++) { sum += lv[i * l.column + k] * rtv[j * rt.column + k]; } ret[i * r.column + j] = sum; } } return new Matrix<T>(l.row, r.column, ret); } public static bool operator ==(Matrix<T> lhs, Matrix<T> rhs) => lhs.Equals(rhs); public static bool operator !=(Matrix<T> lhs, Matrix<T> rhs) => !(lhs == rhs); public Matrix<T> Pow(long n) => Pow(this, n); public static Matrix<T> Pow(Matrix<T> x, long n) { if (x.column != x.row) throw new ArgumentException(); var ret = new Matrix<T>(x.column, x.column); for (int i = 0; i < x.column; i++) { ret[i, i] = T.One; } for (long i = 1; i <= n; i *= 2, x *= x) { if (n / i % 2 == 1) ret *= x; } return ret; } public Matrix<T> Transpose() { var res = new Matrix<T>(this.column, this.row); for (int i = 0; i < this.row; i++) { for (int j = 0; j < this.column; j++) { res[j, i] = this[i, j]; } } return res; } public T Determinant() { if (column != row) throw new ArgumentException(); var a = new T[row * column]; value.AsSpan().CopyTo(a); var swap = false; var p = Enumerable.Range(0, row).ToArray(); for (int i = 0; i < row; i++) { var ok = false; for (int j = i; j < row; j++) { if (a[p[j] * row + i] != T.Zero) { ok = true; if (i != j) { (p[i], p[j]) = (p[j], p[i]); swap = !swap; } break; } } if (!ok) return T.AdditiveIdentity; var t = a[p[i] * row + i]; for (int j = i + 1; j < row; j++) { var c = a[p[j] * row + i] / t; for (int k = 0; k < row; k++) { a[p[j] * row + k] -= c * a[p[i] * row + k]; } } } var det = T.MultiplicativeIdentity; if (swap) det = -det; for (int i = 0; i < row; i++) { det *= a[p[i] * row + i]; } return det; } public T[][] ToRowArray() { var ret = new T[row][]; for (int i = 0; i < row; i++) { ret[i] = this[i].ToArray(); } return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override bool Equals(object? obj) => obj is Matrix<T> x && Equals(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Equals(Matrix<T> other) { if (row != other.row) return false; if (column != other.column) return false; return value.AsSpan().SequenceEqual(other.value); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override int GetHashCode() => HashCode.Combine(row, value); public override string ToString() { var sb = new StringBuilder(); for (int i = 0; i < row; i++) { sb.Append("{ "); for (int j = 0; j < column; j++) { sb.Append(this[i, j]); if (j < column - 1) { sb.Append(", "); } } sb.Append(" }"); if (i < row - 1) { sb.AppendLine(); } } return sb.ToString(); } public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)value).GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); IEnumerator<IEnumerable<T>> IEnumerable<IEnumerable<T>>.GetEnumerator() { for (int i = 0; i < row; i++) { yield return GetRow(i); } } IEnumerable<T> GetRow(int idx) { if (idx < 0 || row <= idx) throw new ArgumentException(); for (int i = 0; i < column; i++) { yield return value[idx * column + i]; } } } }
namespace CpLibrary { public static partial class StaticItems { public static bool NextPermutation<T>(IList<T> arr) where T : IComparable<T> { var p = -1; var q = -1; for (int i = 0; i < arr.Count - 1; i++) { if (arr[i].CompareTo(arr[i + 1]) < 0) p = i; } if (p == -1) return false; for (int i = arr.Count - 1; i >= 0; i--) { if (arr[p].CompareTo(arr[i]) < 0) { q = i; break; } } (arr[p], arr[q]) = (arr[q], arr[p]); for (int i = 0; p + 1 + i < arr.Count - 1 - i; i++) { (arr[p + 1 + i], arr[arr.Count - 1 - i]) = (arr[arr.Count - 1 - i], arr[p + 1 + i]); } return true; } } }
namespace CpLibrary { public static partial class StaticItems { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(uint n) { n = (n & 0x55555555) + (n >> 1 & 0x55555555); n = (n & 0x33333333) + (n >> 2 & 0x33333333); n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f); n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff); n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff); return (int)n; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(int n) => PopCount((uint)n); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(ulong n) { n = (n & 0x5555555555555555) + (n >> 1 & 0x5555555555555555); n = (n & 0x3333333333333333) + (n >> 2 & 0x3333333333333333); n = (n & 0x0f0f0f0f0f0f0f0f) + (n >> 4 & 0x0f0f0f0f0f0f0f0f); n = (n & 0x00ff00ff00ff00ff) + (n >> 8 & 0x00ff00ff00ff00ff); n = (n & 0x0000ffff0000ffff) + (n >> 16 & 0x0000ffff0000ffff); n = (n & 0x00000000ffffffff) + (n >> 32 & 0x00000000ffffffff); return (int)n; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(long n) => PopCount((ulong)n); } }
namespace CpLibrary { public static partial class StaticItems { public static Graph.Graph.DirectedGraph NextGraph(this IRandom rand, int n, int m) { throw new NotImplementedException(); } } }
namespace CpLibrary { public static partial class StaticItems { public static T[][] ReadMatrix<T>(this Scanner sr, int n, int m) where T : ISpanParsable<T> => Enumerable.Range(0, n).Select(p => sr.ReadValueArray<T>(m)).ToArray(); public static T[][] ReadJaggedArray<T>(this Scanner sr, int n, int[] m) where T : ISpanParsable<T> => Enumerable.Range(0, n).Select(p => sr.ReadValueArray<T>(m[p])).ToArray(); } }
namespace CpLibrary { public static partial class StaticItems { public static int[] dx4 => new int[] { 1, 0, -1, 0 }; public static int[] dy4 => new int[] { 0, 1, 0, -1 }; public static int[] dx8 => new int[] { 1, 1, 0, -1, -1, -1, 0, 1 }; public static int[] dy8 => new int[] { 0, 1, 1, 1, 0, -1, -1, -1 }; public enum YesNoOption { Normal, Upper, Lower } public static string YesNo(bool condition, YesNoOption option = YesNoOption.Normal) { if (option == YesNoOption.Normal) return YesNoNormal(condition); else if (option == YesNoOption.Upper) return YesNoUpper(condition); else if (option == YesNoOption.Lower) return YesNoLower(condition); else throw new ArgumentException(); } public static string YesNoNormal(bool condition) => condition ? "Yes" : "No"; public static string YesNoUpper(bool condition) => condition ? "YES" : "NO"; public static string YesNoLower(bool condition) => condition ? "yes" : "no"; public static T SignOutput<T>(int x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T SignOutput<T>(long x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T SignOutput<T>(double x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T[] CreateArray<T>(int n, Func<int, T> func) => Enumerable.Range(0, n).Select(p => func(p)).ToArray(); public static T[][] CreateArray<T>(int x, int y, Func<int, int, T> func) => Enumerable.Range(0, x).Select(i => Enumerable.Range(0, y).Select(j => func(i, j)).ToArray()).ToArray(); public static T[][][] CreateArray<T>(int x, int y, int z, Func<int, int, int, T> func) => Enumerable.Range(0, x).Select(i => Enumerable.Range(0, y).Select(j => Enumerable.Range(0, z).Select(k => func(i, j, k)).ToArray()).ToArray()).ToArray(); } }
namespace CpLibrary { public static partial class StaticItems { public static void WriteMatrix<T>(this StreamWriter sw, IEnumerable<IEnumerable<T>> arr) => sw.WriteLine(arr.Select(p => p.Join(" ")).Join("\n")); public static void WriteMatrix<T>(this StreamWriter sw, Matrix<T> arr) where T : INumberBase<T> => sw.WriteMatrix((IEnumerable<IEnumerable<T>>)arr); } }
namespace CpLibrary.Util { public interface IRandom { public int Next(); public int Next(int b); public int Next(int a, int b); public void NextBytes(byte[] b); public void NextBytes(Span<byte> b); public double NextDouble(); public long NextLong(); public long NextLong(long b); public long NextLong(long a, long b); } }
#endregion Expanded by https://github.com/kzrnm/SourceExpander