結果

問題 No.1972 Modulo Set
ユーザー masayamatumasayamatu
提出日時 2022-06-17 15:04:30
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 7,386 bytes
コンパイル時間 11,976 ms
コンパイル使用メモリ 167,692 KB
実行使用メモリ 214,800 KB
最終ジャッジ日時 2024-10-08 17:56:13
合計ジャッジ時間 17,811 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
30,320 KB
testcase_01 AC 55 ms
30,208 KB
testcase_02 AC 56 ms
30,208 KB
testcase_03 AC 79 ms
34,176 KB
testcase_04 AC 88 ms
36,480 KB
testcase_05 AC 90 ms
37,240 KB
testcase_06 AC 116 ms
40,320 KB
testcase_07 AC 146 ms
46,720 KB
testcase_08 AC 92 ms
37,760 KB
testcase_09 AC 62 ms
30,848 KB
testcase_10 AC 86 ms
36,608 KB
testcase_11 AC 137 ms
44,160 KB
testcase_12 AC 74 ms
33,392 KB
testcase_13 AC 66 ms
31,616 KB
testcase_14 AC 67 ms
31,872 KB
testcase_15 AC 166 ms
45,432 KB
testcase_16 AC 187 ms
47,488 KB
testcase_17 AC 100 ms
36,224 KB
testcase_18 AC 57 ms
30,208 KB
testcase_19 AC 168 ms
45,056 KB
testcase_20 AC 194 ms
47,744 KB
testcase_21 AC 114 ms
38,016 KB
testcase_22 AC 155 ms
43,904 KB
testcase_23 AC 290 ms
57,856 KB
testcase_24 AC 143 ms
41,344 KB
testcase_25 AC 190 ms
45,824 KB
testcase_26 AC 203 ms
51,824 KB
testcase_27 AC 301 ms
58,216 KB
testcase_28 AC 144 ms
41,344 KB
testcase_29 AC 186 ms
45,568 KB
testcase_30 AC 245 ms
52,096 KB
testcase_31 AC 65 ms
31,360 KB
testcase_32 AC 220 ms
50,176 KB
testcase_33 AC 344 ms
60,152 KB
testcase_34 AC 343 ms
59,784 KB
testcase_35 AC 346 ms
59,776 KB
testcase_36 AC 343 ms
214,800 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (93 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/

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
//using static CompLib.CompLib;
//using DataStructure;

namespace atcoder
{

    class Program
    {
        const int intMax = 1000000000;
        const long longMax = 2000000000000000000;
        static void Main(string[] args)
        {
            var NM = Console.ReadLine().Trim().Split().Select(long.Parse).ToArray();
            var A = Console.ReadLine().Trim().Split().Select(long.Parse).ToArray();
            for (int i = 0; i < NM[0]; i++)
            {
                A[i] %= NM[1];
            }
            var list = new Dictionary<long, int>();
            var set = new Set<long>();
            for (int i = 0; i < NM[0]; i++)
            {
                if (!list.ContainsKey(A[i]))
                {
                    list.Add(A[i], 1);
                }
                else
                {
                    list[A[i]]++;
                }
                set.Add(Math.Min(A[i], NM[1] - A[i]));
                if (!list.ContainsKey(Math.Min(A[i], NM[1] - A[i])))
                    list.Add(Math.Min(A[i], NM[1] - A[i]), 0);
            }
            long ans = NM[0];
            for (int i = 0; i < set.Count; i++)
            {
                if (set[i] == 0 || set[i] * 2 == NM[1])
                {
                    ans -= list[set[i]] - 1;
                    list[set[i]] = 0;
                }
                else if (list.ContainsKey(NM[1] - set[i]))
                {
                    ans -= Math.Min(list[NM[1] - set[i]], list[set[i]]);
                    list[NM[1] - set[i]] = 0;
                    list[set[i]] = 0;
                }
            }
            Console.WriteLine(ans);
        }
    }
    public class Set<T>
    {
        Node root;
        readonly IComparer<T> comparer;
        readonly Node nil;
        public bool IsMultiSet { get; set; }
        public Set(IComparer<T> comparer)
        {
            nil = new Node(default(T));
            root = nil;
            this.comparer = comparer;
        }
        public Set(Comparison<T> comaprison) : this(Comparer<T>.Create(comaprison)) { }
        public Set() : this(Comparer<T>.Default) { }
        public bool Add(T v)
        {
            return insert(ref root, v);
        }
        public bool Remove(T v)
        {
            return remove(ref root, v);
        }
        public T this[int index] { get { return find(root, index); } }
        public int Count { get { return root.Count; } }
        public void RemoveAt(int k)
        {
            if (k < 0 || k >= root.Count) throw new ArgumentOutOfRangeException();
            removeAt(ref root, k);
        }
        public T[] Items
        {
            get
            {
                var ret = new T[root.Count];
                var k = 0;
                walk(root, ret, ref k);
                return ret;
            }
        }
        void walk(Node t, T[] a, ref int k)
        {
            if (t.Count == 0) return;
            walk(t.lst, a, ref k);
            a[k++] = t.Key;
            walk(t.rst, a, ref k);
        }
 
        bool insert(ref Node t, T key)
        {
            if (t.Count == 0) { t = new Node(key); t.lst = t.rst = nil; t.Update(); return true; }
            var cmp = comparer.Compare(t.Key, key);
            bool res;
            if (cmp > 0)
                res = insert(ref t.lst, key);
            else if (cmp == 0)
            {
                if (IsMultiSet) res = insert(ref t.lst, key);
                else return false;
            }
            else res = insert(ref t.rst, key);
            balance(ref t);
            return res;
        }
        bool remove(ref Node t, T key)
        {
            if (t.Count == 0) return false;
            var cmp = comparer.Compare(key, t.Key);
            bool ret;
            if (cmp < 0) ret = remove(ref t.lst, key);
            else if (cmp > 0) ret = remove(ref t.rst, key);
            else
            {
                ret = true;
                var k = t.lst.Count;
                if (k == 0) { t = t.rst; return true; }
                if (t.rst.Count == 0) { t = t.lst; return true; }
 
 
                t.Key = find(t.lst, k - 1);
                removeAt(ref t.lst, k - 1);
            }
            balance(ref t);
            return ret;
        }
        void removeAt(ref Node t, int k)
        {
            var cnt = t.lst.Count;
            if (cnt < k) removeAt(ref t.rst, k - cnt - 1);
            else if (cnt > k) removeAt(ref t.lst, k);
            else
            {
                if (cnt == 0) { t = t.rst; return; }
                if (t.rst.Count == 0) { t = t.lst; return; }
 
                t.Key = find(t.lst, k - 1);
                removeAt(ref t.lst, k - 1);
            }
            balance(ref t);
        }
        void balance(ref Node t)
        {
            var balance = t.lst.Height - t.rst.Height;
            if (balance == -2)
            {
                if (t.rst.lst.Height - t.rst.rst.Height > 0) { rotR(ref t.rst); }
                rotL(ref t);
            }
            else if (balance == 2)
            {
                if (t.lst.lst.Height - t.lst.rst.Height < 0) rotL(ref t.lst);
                rotR(ref t);
            }
            else t.Update();
        }
 
        T find(Node t, int k)
        {
            if (k < 0 || k > root.Count) throw new ArgumentOutOfRangeException();
            for (; ; )
            {
                if (k == t.lst.Count) return t.Key;
                else if (k < t.lst.Count) t = t.lst;
                else { k -= t.lst.Count + 1; t = t.rst; }
            }
        }
        public int LowerBound(T v)
        {
            var k = 0;
            var t = root;
            for (; ; )
            {
                if (t.Count == 0) return k;
                if (comparer.Compare(v, t.Key) <= 0) t = t.lst;
                else { k += t.lst.Count + 1; t = t.rst; }
            }
        }
        public int UpperBound(T v)
        {
            var k = 0;
            var t = root;
            for (; ; )
            {
                if (t.Count == 0) return k;
                if (comparer.Compare(t.Key, v) <= 0) { k += t.lst.Count + 1; t = t.rst; }
                else t = t.lst;
            }
        }
 
        void rotR(ref Node t)
        {
            var l = t.lst;
            t.lst = l.rst;
            l.rst = t;
            t.Update();
            l.Update();
            t = l;
        }
        void rotL(ref Node t)
        {
            var r = t.rst;
            t.rst = r.lst;
            r.lst = t;
            t.Update();
            r.Update();
            t = r;
        }
        class Node
        {
            public Node(T key)
            {
                Key = key;
            }
            public int Count { get; private set; }
            public sbyte Height { get; private set; }
            public T Key { get; set; }
            public Node lst, rst;
            public void Update()
            {
                Count = 1 + lst.Count + rst.Count;
                Height = (sbyte)(1 + Math.Max(lst.Height, rst.Height));
            }
            public override string ToString()
            {
                return string.Format("Count = {0}, Key = {1}", Count, Key);
            }
        }
    }
}
0