結果
問題 | No.2696 Sign Creation |
ユーザー | crimsontea |
提出日時 | 2024-03-22 23:09:06 |
言語 | C# (.NET 8.0.203) |
結果 |
TLE
|
実行時間 | - |
コード長 | 23,258 bytes |
コンパイル時間 | 8,103 ms |
コンパイル使用メモリ | 169,832 KB |
実行使用メモリ | 45,852 KB |
最終ジャッジ日時 | 2024-05-17 18:18:53 |
合計ジャッジ時間 | 13,353 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
35,072 KB |
testcase_01 | AC | 65 ms
38,300 KB |
testcase_02 | AC | 67 ms
31,092 KB |
testcase_03 | AC | 65 ms
30,720 KB |
testcase_04 | AC | 65 ms
30,720 KB |
testcase_05 | AC | 66 ms
31,232 KB |
testcase_06 | AC | 67 ms
31,232 KB |
testcase_07 | AC | 66 ms
31,360 KB |
testcase_08 | AC | 99 ms
34,560 KB |
testcase_09 | AC | 79 ms
33,536 KB |
testcase_10 | AC | 113 ms
34,656 KB |
testcase_11 | AC | 92 ms
33,408 KB |
testcase_12 | AC | 90 ms
33,664 KB |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (97 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(105,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(106,30): 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 A; using AtCoder; using AtCoder.Internal; using System; using System.Buffers; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Numerics; using System.Runtime.CompilerServices; using static A.InputUtility; class Program { static void Main() { using Output output = new(false); InputNewLine(); var (h, w, n, d) = (NextInt32, NextInt32, NextInt32, NextInt32); var a = new (int x, int y)[n]; for (int i = 0; i < a.Length; i++) { InputNewLine(); a[i] = (NextInt32, NextInt32); } Dsu dsu = new(n); for (int i = 0; i < a.Length; i++) { var (x1, y1) = a[i]; for (int k = i + 1; k < a.Length; k++) { var (x2, y2) = a[k]; var dist = Math.Abs(x1 - x2) + Math.Abs(y1 - y2); if (dist <= d) { dsu.Merge(i, k); } } } var dict = a.Enumerate().ToDictionary(x => x.item, x => x.index); var set = a.ToHashSet(); var count = dsu.Groups().Count(x => x.Length >= 2); var max = 0; var min = n; HashSet<int> groups = new(); HashSet<int> groupsU = new(); for (int y = 1; y <= h; y++) { for (int x = 1; x <= w; x++) { if (set.Contains((x, y))) continue; groups.Clear(); groupsU.Clear(); for (int yd = -d; yd <= d; yd++) { var u = Math.Abs(d - Math.Abs(yd)); for (int xd = -u; xd <= u; xd++) { var nx = x + xd; var ny = y + yd; if (0 >= nx || nx > w || 0 >= ny || ny > h) { continue; } if (dict.TryGetValue((nx, ny), out int index)) { if (dsu.Size(index) >= 2) { groups.Add(dsu.Leader(index)); } else { groupsU.Add(dsu.Leader(index)); } } } } var nCount = count + (groupsU.Count >= 1 ? 1 : 0) - Math.Max(0, (groups.Count - 1)); max = Math.Max(max, nCount); min = Math.Min(min, nCount); } } Console.WriteLine($"{min} {max}"); } } namespace A { public static class InputUtility { private static string[]? s_inputs; private static string? s_raw; private static int s_index = 0; private static void Init() => s_index = 0; public static int NextInt32 => int.Parse(s_inputs![s_index++]!); public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!); public static long NextInt64 => long.Parse(s_inputs![s_index++]!); public static ulong NextUInt64 => ulong.Parse(s_inputs![s_index++]!); public static string NextString => s_inputs![s_index++]; public static char NextChar => s_inputs![s_index++][0]; public static decimal NextDecimal => decimal.Parse(s_inputs![s_index++]!); public static BigInteger NextBigInteger => BigInteger.Parse(s_inputs![s_index++]!); public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray(); public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray(); public static string[] GetStringArray() => s_inputs!; public static string GetRawString() => s_raw!; #if DEBUG private static TextReader? s_textReader; public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path)); #endif public static bool InputNewLine() { #if DEBUG if (s_textReader is TextReader sr) { Init(); s_raw = sr.ReadLine()!; s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries); return true; } #endif Init(); s_raw = Console.ReadLine()!; s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries); return true; } } public static class CombinationFunction { public static void PartedRotate<T>(T[] a, int first1, int last1, int first2, int last2) { if (first1 == last1 || first2 == last2) return; int next = first2; while (first1 != next) { Swap(a, first1++, next++); if (first1 == last1) first1 = first2; if (next == last2) { next = first2; } else if (first1 == first2) { first2 = next; } } } public static bool NextCombinationImp<T>(T[] a, int first1, int last1, int first2, int last2) where T : IComparable<T> { if (first1 == last1 || first2 == last2) return false; int target = last1 - 1; int lastElem = last2 - 1; while (target != first1 && !(a[target].CompareTo(a[lastElem]) < 0)) target--; if (target == first1 && !(a[target].CompareTo(a[lastElem]) < 0)) { PartedRotate(a, first1, last1, first2, last2); return false; } int next = first2; while (!(a[target].CompareTo(a[next]) < 0)) next++; Swap(a, target++, next++); PartedRotate(a, target, last1, next, last2); return true; } public static bool NextCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T> => NextCombinationImp(a, first, mid, mid, last); public static bool PrevCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T> => NextCombinationImp(a, mid, last, first, mid); public static void Swap<T>(T[] a, int i, int j) => (a[i], a[j]) = (a[j], a[i]); } public static class PermutationFunction { public static bool NextPermutation<T>(T[] a) where T : IComparable<T> { int n = a.Length; int i = n - 2; while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; } if (i < 0) { return false; } int j = n - 1; while (a[j].CompareTo(a[i]) <= 0) { j--; } (a[i], a[j]) = (a[j], a[i]); Array.Reverse(a, i + 1, n - i - 1); return true; } public static bool NextPermutation<T>(Span<T> a) where T : IComparable<T> { int n = a.Length; int i = n - 2; while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; } if (i < 0) { return false; } int j = n - 1; while (a[j].CompareTo(a[i]) <= 0) { j--; } (a[i], a[j]) = (a[j], a[i]); a.Slice(i + 1, n - i - 1).Reverse(); return true; } } public readonly struct Output : IDisposable { private readonly StreamWriter _sw; #if DEBUG public Output(string path) { var fs = new FileStream(path, FileMode.Create, FileAccess.Write); _sw = new StreamWriter(fs); Console.SetOut(_sw); } #endif public Output(bool autoFlush) { _sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush }; Console.SetOut(_sw); } public void Dispose() { _sw.Dispose(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal void Flush() { _sw.Flush(); } } public static class ArrayExtensions { public static void Swap<T>(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]); public static int LowerBound<T>(this T[] a, T target) where T : IComparable<T> { int ok = a.Length; int ng = -1; while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid) (ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid); return ok; } public static int UpperBound<T>(this T[] a, T target) where T : IComparable<T> { int ok = a.Length; int ng = -1; while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid) (ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid); return ok; } public struct IndexedEnumerable<T> : IEnumerable<(T item, int index)> { private readonly T[] _a; private readonly int _startIndex; public IndexedEnumerable(T[] a, int startIndex = 0) { _a = a; _startIndex = startIndex; } public readonly IndexedEnumerator<T> GetEnumerator() => new IndexedEnumerator<T>(_a, _startIndex); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator(); } public struct IndexedEnumerator<T> : IEnumerator<(T item, int index)> { public readonly (T item, int index) Current => (_a[_index], _index + _startIndex); private int _index; private int _startIndex; private T[] _a; public IndexedEnumerator(T[] a, int startIndex) { _index = -1; _a = a; _startIndex = startIndex; } public bool MoveNext() => ++_index < _a.Length; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public void Reset() => _index = -1; } /// <returns>(T value, int index)</returns> public static IndexedEnumerable<T> Enumerate<T>(this T[] arr, int startIndex = 0) => new IndexedEnumerable<T>(arr, startIndex); } public static class IEnumerableExtensions { public static IEnumerable<TSource> Log<TSource>(this IEnumerable<TSource> source) { Console.WriteLine(string.Join(' ', source)); return source; } public static ScanEnumerable<TSource, TAccumulate> Scan<TSource, TAccumulate>( this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> accumulator) where TSource : struct where TAccumulate : struct { return new ScanEnumerable<TSource, TAccumulate>(source, accumulator, seed); } public static IEnumerable<TAccumulate> ScanExSeed<TSource, TAccumulate>( this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> accumulator) { var accumulation = new List<TAccumulate>(); var current = seed; foreach (var item in source) { current = accumulator(current, item); accumulation.Add(current); } return accumulation; } public readonly struct ScanEnumerable<TSource, TAccumulate> : IEnumerable<TAccumulate> where TSource : struct where TAccumulate : struct { private readonly IEnumerable<TSource> _source; private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator; private readonly TAccumulate _seed; public ScanEnumerable(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed) { _source = source; _accumulator = accumulator; _seed = seed; } public readonly ScanEnumerator<TSource, TAccumulate> GetEnumerator() => new(_source, _accumulator, _seed); readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); readonly IEnumerator<TAccumulate> IEnumerable<TAccumulate>.GetEnumerator() => GetEnumerator(); } public struct ScanEnumerator<TSource, TAccumulate> : IEnumerator<TAccumulate> where TSource : struct where TAccumulate : struct { private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator; private readonly IEnumerator<TSource> _enumerator; private TAccumulate _current; private bool _secondOrLaterElement = false; public ScanEnumerator(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed) { _enumerator = source.GetEnumerator(); _accumulator = accumulator; _current = seed; } public readonly TAccumulate Current => _current; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { if (_enumerator.MoveNext()) { _current = _accumulator(_current, _enumerator.Current); return true; } return false; } else { _secondOrLaterElement = true; return true; } } public void Reset() { throw new NotSupportedException(); } } public static IEnumerable<TSource> Scan<TSource>( this IEnumerable<TSource> source, Func<TSource, TSource, TSource> accumulator) { if (source is null) throw new ArgumentNullException(paramName: nameof(source)); if (accumulator is null) throw new ArgumentNullException(paramName: nameof(accumulator)); var accumulation = new List<TSource>(); if (source.Any() is false) { return accumulation; } var current = source.First(); accumulation.Add(current); foreach (var item in source.Skip(1)) { current = accumulator(current, item); accumulation.Add(current); } return accumulation; } public static CombinationEnumerable<T> Combination<T>(this T[] a, int k) where T : IComparable<T> => new(a, k); public readonly struct CombinationEnumerable<T> where T : IComparable<T> { private readonly T[] _a; private readonly int _k; public CombinationEnumerable(T[] a, int k) { _a = a; _k = k; } public readonly CombinationEnumerator<T> GetEnumerator() => new(_a, _k); } public struct CombinationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T> { private readonly int _k; private readonly T[] _a; private readonly int _n; private bool _secondOrLaterElement = false; public CombinationEnumerator(T[] a, int k) { _a = a; _n = a.Length; _k = k; } public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[.._k]; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { return CombinationFunction.NextCombination(_a, 0, _k, _n); } else { _secondOrLaterElement = true; return true; } } public void Reset() { throw new NotSupportedException(); } } public static PermutationEnumerable<T> Permutation<T>(this T[] a) where T : IComparable<T> => new(a); public static PermutationEnumerable<T> Permutation<T>(this Span<T> a) where T : IComparable<T> => new(a); public readonly ref struct PermutationEnumerable<T> where T : IComparable<T> { private readonly Span<T> _a; public PermutationEnumerable(T[] a) => _a = a; public PermutationEnumerable(Span<T> a) => _a = a; public readonly PermutationEnumerator<T> GetEnumerator() => new(_a); } public ref struct PermutationEnumerator<T> where T : IComparable<T> { private readonly Span<T> _a; private readonly int _n; private bool _secondOrLaterElement = false; public PermutationEnumerator(T[] a) { _a = a; _n = a.Length; } public PermutationEnumerator(Span<T> a) { _a = a; _n = a.Length; } public readonly ReadOnlyMemory<T> Current => _a.ToArray().AsMemory()[..]; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { return PermutationFunction.NextPermutation(_a); } else { _secondOrLaterElement = true; return true; } } public void Reset() => throw new NotSupportedException(); } } public class MyMath { public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x); public static long Pow10(int y) => Pow(10, y); public static long Pow2(int y) => Pow(2, y); public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b); public static long Lcm(long a, long b) => a / Gcd(a, b) * b; } public class MyMathBigInteger { public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x); public static BigInteger Pow10(int y) => Pow(10, y); public static BigInteger Pow2(int y) => Pow(2, y); } } #region Expanded by https://github.com/kzrnm/SourceExpander namespace AtCoder{public class Dsu{public readonly int[]_parentOrSize;public Dsu(int n){_parentOrSize=new int[n];_parentOrSize.AsSpan().Fill(-1);}[MethodImpl(256)]public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_parentOrSize[x]<-_parentOrSize[y])(x,y)=(y,x);_parentOrSize[x]+=_parentOrSize[y];_parentOrSize[y]=x;return x;}[MethodImpl(256)]public bool Same(int a,int b){return Leader(a)==Leader(b);}[MethodImpl(256)]public int Leader(int a){if(_parentOrSize[a]<0)return a;while(0<=_parentOrSize[_parentOrSize[a]]){(a,_parentOrSize[a])=(_parentOrSize[a],_parentOrSize[_parentOrSize[a]]);}return _parentOrSize[a];}[MethodImpl(256)]public int Size(int a){return-_parentOrSize[Leader(a)];}[MethodImpl(256)]public int[][]Groups(){int n=_parentOrSize.Length;int[]leaderBuf=new int[n];int[]id=new int[n];var resultList=new SimpleList<int[]>(n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_parentOrSize[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}} namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{public T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}[MethodImpl(256)]public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);[MethodImpl(256)]public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(256)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}[MethodImpl(256)]public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}[MethodImpl(256)]public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public void RemoveLast(int size){if((Count-=size)<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}[MethodImpl(256)]public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}[MethodImpl(256)]public void Clear()=>Count=0;[MethodImpl(256)]public bool Contains(T item)=>IndexOf(item)>=0;[MethodImpl(256)]public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);[MethodImpl(256)]public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);[MethodImpl(256)]public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}[MethodImpl(256)]public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}} namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander