#1089394 (C#) No.3167 [Cherry 7th Tune C] Cut in Queue

• 問題: No.3167 [Cherry 7th Tune C] Cut in Queue
• ユーザー: tobisatis
• 提出日時: 2025-05-31 02:23:35
• 言語: C# (.NET 8.0.404)
• 結果: TLE
• 実行時間: -
• コード長: 8,091 bytes
• コンパイル時間: 7,250 ms
• コンパイル使用メモリ: 171,312 KB
• 実行使用メモリ: 112,684 KB
• 最終ジャッジ日時: 2025-05-31 02:24:01
• 合計ジャッジ時間: 24,506 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 8 TLE * 3 -- * 32

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (85 ミリ秒)。
  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 az = n.Repeat(() => Int() - 1);
    var q = Int();
    var queries = new (int, int)[q];
    for (var i = 0; i < q; i++)
    {
        var kind = Int();
        var v = -1;
        if (kind != 2) v = Int() - 1;
        queries[i] = (kind, v);
    }

    var fa = new FlexibleArray<int>(n + q);
    for (var i = 0; i < n; i++) fa.Insert(az[i]);
    var lb = n - 1;
    var ans = new List<int>();
    foreach (var (t, v) in queries)
    {
        if (t == 1)
        {
            lb++;
            if (v < 0) fa.Insert(lb);
            else
            {
                var i = fa.FindFirst(v)!.Value;
                fa.Insert(lb, i);
            }
        }
        if (t == 2) fa.DeleteAt(0);
        if (t == 3)
        {
            var vns = fa.At(v);
            ans.Add(vns + 1);
        }
    }
    Out(ans);
}

#region
var _io_ = new AtCoderIO(){ Backend = new() };
Run();
_io_.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; }

    ReadOnlyMemory<string> _input = Array.Empty<string>();
    int _iter = 0;
    public string Next()
    {
        while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Trim().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 StreamReader _sr = new("input.txt");
    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();
}

class Bag<K> where K : notnull
{
    readonly Dictionary<K, int> _dictionary = new();
    public void Add(K key)
    {
        var dictionary = _dictionary;
        if (dictionary.TryGetValue(key, out var count)) dictionary[key] = count + 1;
        else dictionary[key] = 1;
    }
    public void Remove(K key)
    {
        var dictionary = _dictionary;
        if (!dictionary.TryGetValue(key, out var count)) return;
        if (count == 1) dictionary.Remove(key);
        else dictionary[key] = count - 1;
    }
    public int this[K key] => _dictionary.TryGetValue(key, out var count) ? count : 0;
    public int CountKeys => _dictionary.Count;
}

class FlexibleArray<T> where T : notnull
{
    class U
    {
        readonly LinkedList<T> _values = new();
        readonly Bag<T> _bag = new();

        public void InsertAt(T value, int index)
        {
            _bag.Add(value);
            if (index == 0) _values.AddFirst(value);
            else _values.AddAfter(NodeAt(index - 1), value);
        }

        public void InsertLast(T value)
        {
            _bag.Add(value);
            _values.AddLast(value);
        }

        public T DeleteAt(int index)
        {
            var node = NodeAt(index);
            var res = node.Value;
            _bag.Remove(res);
            _values.Remove(node);
            return res;
        }

        public T DeleteLast()
        {
            var res = _values.Last!.Value;
            _bag.Remove(res);
            _values.RemoveLast();
            return res;
        }

        public T At(int index) => NodeAt(index).Value;

        public int FindFirst(T value)
        {
            var i = 0;
            var node = _values.First;
            while (node != null)
            {
                if (node.Value.Equals(value)) return i;
                node = node.Next;
                i++;
            }
            throw new Exception("value not found");
        }

        public int Count => _values.Count;
        public int CountValue(T value) => _bag[value];

        LinkedListNode<T> NodeAt(int index)
        {
            var res = _values.First!;
            for (var i = 0; i < index; i++) res = res.Next!;
            return res;
        }
    }

    readonly LinkedList<U> _data;
    readonly int _bucketSizeBase;

    public FlexibleArray(int size)
    {
        size = Math.Max(size, 4);
        var sqrt = 1;
        while (sqrt * sqrt < size) sqrt++;
        _bucketSizeBase = sqrt;
        var first = new U();
        _data = new();
        _data.AddFirst(first);
    }

    public void Insert(T value, int before = -1)
    {
        Count++;
        if (before < 0)
        {
            var ln = _data.Last!;
            var u = ln.Value;
            u.InsertLast(value);
            if (u.Count == _bucketSizeBase << 1)
            {
                var prev = new U();
                for (var i = 0; i < _bucketSizeBase; i++)
                {
                    var deleted = u.DeleteAt(0);
                    prev.InsertLast(deleted);
                }
                _data.AddBefore(ln, prev);
            }
            return;
        }
        var node = _data.First;
        while (node != null)
        {
            var u = node.Value;
            if (before >= u.Count)
            {
                before -= u.Count;
                node = node.Next;
                continue;
            }
            u.InsertAt(value, before);
            if (u.Count == _bucketSizeBase << 1)
            {
                var next = new U();
                for (var i = 0; i < _bucketSizeBase; i++)
                {
                    var deleted = u.DeleteLast();
                    next.InsertAt(deleted, 0);
                }
                _data.AddAfter(node, next);
            }
            return;
        }
        Count--;
        throw new IndexOutOfRangeException();
    }

    public void DeleteAt(int index)
    {
        Count--;
        var node = _data.First;
        while (node != null)
        {
            var u = node.Value;
            if (index >= u.Count)
            {
                index -= u.Count;
                node = node.Next;
                continue;
            }
            u.DeleteAt(index);
            if (u.Count == _bucketSizeBase >> 1)
            {
                var next = node.Next;
                var prev = node.Previous;
                var count = u.Count;
                if (next != null)
                {
                    var v = next.Value;
                    for (var i = 0; i < count; i++)
                    {
                        var deleted = u.DeleteLast();
                        v.InsertAt(deleted, 0);
                    }
                }
                else if (prev != null)
                {
                    var v = prev.Value;
                    for (var i = 0; i < count; i++)
                    {
                        var deleted = u.DeleteAt(0);
                        v.InsertLast(deleted);
                    }
                }
            }
            return;
        }
        Count++;
        throw new IndexOutOfRangeException();
    }

    public T At(int index)
    {
        foreach (var u in _data)
        {
            if (index < u.Count) return u.At(index);
            index -= u.Count;
        }
        throw new IndexOutOfRangeException();
    }

    public int? FindFirst(T value)
    {
        var res = 0;
        foreach (var u in _data)
        {
            if (u.CountValue(value) > 0) return res + u.FindFirst(value);
            res += u.Count;
        }
        return null;
    }

    public int Count { get; private set; }
}