#964329 (C#) No.2696 Sign Creation

提出ソース

結果

問題	No.2696 Sign Creation
ユーザー	crimsontea
提出日時	2024-03-22 23:06:23
言語	C# (.NET 8.0.203)
結果	TLE
実行時間	-
コード長	23,070 bytes
コンパイル時間	8,227 ms
コンパイル使用メモリ	169,796 KB
実行使用メモリ	48,380 KB
最終ジャッジ日時	2024-05-17 18:18:42
合計ジャッジ時間	13,401 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	64 ms 34,816 KB
testcase_01	AC	63 ms 38,300 KB
testcase_02	AC	64 ms 30,720 KB
testcase_03	AC	63 ms 31,228 KB
testcase_04	AC	62 ms 30,848 KB
testcase_05	AC	63 ms 30,848 KB
testcase_06	AC	64 ms 31,232 KB
testcase_07	AC	63 ms 30,848 KB
testcase_08	AC	92 ms 34,560 KB
testcase_09	AC	73 ms 33,536 KB
testcase_10	AC	107 ms 35,068 KB
testcase_11	AC	87 ms 33,536 KB
testcase_12	AC	88 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 を復元しました (94 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(99,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(100,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/

ソースコード

raw source code

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 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 (dict.ContainsKey((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 (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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード