結果
| 問題 | No.1972 Modulo Set |
| ユーザー |
 masayamatu
|
| 提出日時 | 2022-06-17 14:54:34 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,254 bytes |
| コンパイル時間 | 10,551 ms |
| コンパイル使用メモリ | 169,516 KB |
| 実行使用メモリ | 228,352 KB |
| 最終ジャッジ日時 | 2024-10-08 17:33:36 |
| 合計ジャッジ時間 | 30,359 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 RE * 2 |
| other | AC * 5 RE * 29 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (96 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 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]));}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);}}}}