結果
問題 |
No.3075 Mex Recurrence Formula
|
ユーザー |
|
提出日時 | 2025-03-28 22:07:55 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,347 ms / 2,000 ms |
コード長 | 8,196 bytes |
コンパイル時間 | 8,195 ms |
コンパイル使用メモリ | 171,400 KB |
実行使用メモリ | 196,992 KB |
最終ジャッジ日時 | 2025-03-28 22:08:47 |
合計ジャッジ時間 | 38,395 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (105 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable using System.Numerics; void Run() { var n = Int(); var x = long.Parse(String()) - 1; var az = n.Repeat(Int); if (x < n) { Out(az[x]); return; } x -= n; if (x > (n + 1) * 2) x = (x % (n + 1)) + n + 1; var q = new Queue<int>(); var b = new int[n + 1]; var s = new OrderedMultiSet<int>(); for (var i = 0; i <= n; i++) s.Insert(i); foreach (var a in az) { s.Delete(a); if (a <= n) b[a]++; q.Enqueue(a); } while (x > 0) { var min = s.At(0); s.Delete(min); q.Enqueue(min); b[min]++; var t = q.Dequeue(); if (t <= n) { b[t]--; if (b[t] == 0) s.Insert(t); } x--; } Out(s.At(0)); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); class AtCoderIO { public required StandardIOBackend Backend { get; init; } Memory<string> _input = Array.Empty<string>(); int _iter = 0; public string Next() { while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0); return _input.Span[_iter++]; } public void Out(object? x, string? separator = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast<object>(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } Backend.WriteLine(x); } } class StandardIOBackend { readonly StreamReader _sr = new(Console.OpenStandardInput()); readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; public string ReadLine() => _sr.ReadLine()!; public void WriteLine(object? value) => _sw.WriteLine(value); public void Flush() => _sw.Flush(); } #endregion static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } abstract class SelfBalancingTreeBase<T> { protected class Node { public required T Data { get; set; } public Node? L { get; set; } public Node? R { get; set; } public int Height { get; set; } = 1; public int Size { get; set; } = 1; public Node? this[bool right] { get => right ? R : L; set { if (right) R = value; else L = value; } } } protected static Node At(Node? node, int index) { while (node != null) { var ls = Size(node.L); if (index == ls) return node; var right = index > ls; if (right) index -= ls + 1; node = node[right]; } throw new IndexOutOfRangeException(); } protected Node? Root { get; set; } protected static int Size(Node? node) => node?.Size ?? 0; protected static int Height(Node? node) => node?.Height ?? 0; protected static int HeightDiff(Node node) => Height(node.R) - Height(node.L); protected static void Update(Node node) { node.Height = Math.Max(Height(node.L), Height(node.R)) + 1; node.Size = Size(node.L) + Size(node.R) + 1; } protected static Node? DeleteMin(Node node, Node swap) { if (node.L == null) { swap.Data = node.Data; return node.R; } node.L = DeleteMin(node.L, swap); return Balance(node); } protected static Node Balance(Node node) { var diff = HeightDiff(node); if (diff < -1 || 1 < diff) { var right = diff > 0; var next = node[right]!; if (HeightDiff(next) * diff < 0) node[right] = Rotate(next, right); return Rotate(node, !right); } Update(node); return node; } protected static Node Rotate(Node node, bool right) { var n0 = node[!right]!; node[!right] = n0[right]; Update(node); n0[right] = node; Update(n0); return n0; } public bool DeleteAt(int index) => Size(Root) != Size(Root = DeleteAt(Root, index)); static Node? DeleteAt(Node? node, int index) { if (node == null) return null; var ls = Size(node.L); if (index == ls) { if (node.R == null) return node.L; node.R = DeleteMin(node.R, node); } else { var right = index > ls; node[right] = DeleteAt(node[right], right ? index - 1 - ls : index); } return Balance(node); } protected IEnumerator<T> GetEnumerator() { var stack = new Stack<Node>(); var lastR = Root; while (lastR != null || stack.Count > 0) { while (lastR != null) { stack.Push(lastR); lastR = lastR.L; } var last = stack.Pop(); yield return last.Data; lastR = last.R; } } public int Count { get => Size(Root); } } abstract class SelfBalancingTree<TKey, TValue> : SelfBalancingTreeBase<KeyValuePair<TKey, TValue>> where TKey : IComparable<TKey> { public int MaxIndex(TKey key, bool include) => Bound(Root, key, true, include).Item1; public int MinIndex(TKey key, bool include) => Bound(Root, key, false, include).Item1; protected static (int, Node?) Bound(Node? node, TKey key, bool max, bool include) { var index = max ? -1 : 0; Node? res = null; while (node != null) { var comp = key.CompareTo(node.Data.Key); var left = comp < 0 || comp == 0 && (max ^ include); if (!left) index += Size(node.L) + 1; if (max ^ left) res = node; node = left ? node.L : node.R; } return (index, res); } public int CountKey(TKey key) => MaxIndex(key, true) - MaxIndex(key, false); public ValueTuple<TKey>? MaxKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, true, include).Item2); public ValueTuple<TKey>? MinKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, false, include).Item2); static ValueTuple<TKey>? ToOptionalKey(Node? node) => node == null ? null : new(node.Data.Key); protected static Node? Find(Node? node, TKey key) { var res = Bound(node, key, false, true).Item2; return res != null && key.CompareTo(res.Data.Key) == 0 ? res : null; } protected static KeyValuePair<TKey, TValue> CreateData(TKey key, TValue value) => new(key, value); protected void Insert(KeyValuePair<TKey, TValue> data) => Root = Insert(Root, data); static Node Insert(Node? node, KeyValuePair<TKey, TValue> data) { if (node == null) return new Node{ Data = data }; var right = data.Key.CompareTo(node.Data.Key) >= 0; node[right] = Insert(node[right], data); return Balance(node); } public bool Delete(TKey key) => Size(Root) != Size(Root = Delete(Root, key)); static Node? Delete(Node? node, TKey key) { if (node == null) return null; var comp = key.CompareTo(node.Data.Key); if (comp == 0) { if (node.R == null) return node.L; node.R = DeleteMin(node.R, node); } else { var right = comp > 0; node[right] = Delete(node[right], key); } return Balance(node); } } class OrderedMultiSet<T> : SelfBalancingTree<T, ValueTuple> where T : IComparable<T> { public bool Contains(T key) => Find(Root, key) != null; public T At(int index) => At(Root, index).Data.Key; public void Insert(T key) => Insert(CreateData(key, ValueTuple.Create())); public new IEnumerator<T> GetEnumerator() { using var e = base.GetEnumerator(); while (e.MoveNext()) yield return e.Current.Key; } }