Submit Info #49946

Problem Lang User Status Time Memory
Persistent Queue csharp naminodarie AC 332 ms 64.97 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 189 ms 60.47 MiB
example_00 AC 72 ms 5.46 MiB
half_rot_killer2_00 AC 180 ms 60.34 MiB
half_rot_killer_00 AC 212 ms 64.97 MiB
random_00 AC 263 ms 53.20 MiB
random_01 AC 332 ms 61.83 MiB
random_02 AC 83 ms 11.84 MiB
random_2_00 AC 278 ms 50.58 MiB
random_2_01 AC 315 ms 58.20 MiB
random_2_02 AC 78 ms 11.58 MiB
random_3_00 AC 159 ms 42.83 MiB
random_3_01 AC 197 ms 49.95 MiB
random_3_02 AC 69 ms 10.48 MiB
two_stacks_killer_00 AC 201 ms 62.84 MiB

using Kzrnm.Competitive; using Kzrnm.Competitive.IO; using System; using System.Collections; using System.Collections.Generic; using System.Collections.Immutable; using System.Diagnostics; using System.Globalization; using System.IO; using System.Linq; using System.Runtime.CompilerServices; using System.Text; partial class Program { string YesNo(bool b) => b ? "Yes" : "No"; const bool __ManyTestCases = false; [MethodImpl(MethodImplOptions.AggressiveOptimization)] private object Calc() { int Q = cr; var ques = new RealTimeQueue<int>[Q + 1]; ques.Get(-1) = RealTimeQueue<int>.Empty; for (int q = 0; q < Q; q++) { if (cr.Int == 0) { int t = cr; int x = cr; ques[q] = ques.Get(t).Enqueue(x); } else { int t = cr; ques[q] = ques.Get(t).Dequeue(out var v); cw.WriteLine(v); } } return null; } } static class SR { public const string InvalidEmptyOperation = "InvalidEmptyOperation"; } #nullable enable public sealed partial class RealTimeQueue<T> : IImmutableQueue<T> { /// <summary> /// The singleton empty queue. /// </summary> /// <remarks> /// Additional instances representing the empty queue may exist on deserialized instances. /// Actually since this queue is a struct, instances don't even apply and there are no singletons. /// </remarks> private static readonly RealTimeQueue<T> s_EmptyField = new RealTimeQueue<T>(LazyStack.Empty, ImmutableStack<T>.Empty, LazyStack.Empty); /// <summary> /// The end of the queue that enqueued elements are pushed onto. /// </summary> private readonly ImmutableStack<T> _backwards; /// <summary> /// The end of the queue from which elements are dequeued. /// </summary> private readonly LazyStack _forwards; private readonly LazyStack _lazy; internal RealTimeQueue(LazyStack forwards, ImmutableStack<T> backwards, LazyStack lazy) { Debug.Assert(forwards != null); Debug.Assert(backwards != null); Debug.Assert(lazy != null); _forwards = forwards; _backwards = backwards; _lazy = lazy; } private static RealTimeQueue<T> Create(LazyStack forwards, ImmutableStack<T> backwards, LazyStack lazy) { if (!lazy.IsEmpty) return new RealTimeQueue<T>(forwards, backwards, lazy.Pop()); var stack = new LazyStack(forwards, backwards, LazyStack.Empty); return new RealTimeQueue<T>(stack, ImmutableStack<T>.Empty, stack); } /// <summary> /// Gets the empty queue. /// </summary> public RealTimeQueue<T> Clear() { Debug.Assert(s_EmptyField.IsEmpty); return Empty; } /// <summary> /// Gets a value indicating whether this instance is empty. /// </summary> /// <value> /// <c>true</c> if this instance is empty; otherwise, <c>false</c>. /// </value> public bool IsEmpty { get { Debug.Assert(!_forwards.IsEmpty || _backwards.IsEmpty); return _forwards.IsEmpty; } } /// <summary> /// Gets the empty queue. /// </summary> public static RealTimeQueue<T> Empty { get { Debug.Assert(s_EmptyField.IsEmpty); return s_EmptyField; } } /// <summary> /// Gets an empty queue. /// </summary> IImmutableQueue<T> IImmutableQueue<T>.Clear() { Debug.Assert(s_EmptyField.IsEmpty); return this.Clear(); } /// <summary> /// Gets the element at the front of the queue. /// </summary> /// <exception cref="InvalidOperationException">Thrown when the queue is empty.</exception> public T Peek() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } return _forwards.Peek(); } /// <summary> /// Gets a read-only reference to the element at the front of the queue. /// </summary> /// <exception cref="InvalidOperationException">Thrown when the queue is empty.</exception> public ref readonly T PeekRef() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } return ref _forwards.PeekRef(); } /// <summary> /// Adds an element to the back of the queue. /// </summary> /// <param name="value">The value.</param> /// <returns> /// The new queue. /// </returns> public RealTimeQueue<T> Enqueue(T value) { return Create(_forwards, _backwards.Push(value), _lazy); } /// <summary> /// Adds an element to the back of the queue. /// </summary> /// <param name="value">The value.</param> /// <returns> /// The new queue. /// </returns> IImmutableQueue<T> IImmutableQueue<T>.Enqueue(T value) { return this.Enqueue(value); } /// <summary> /// Returns a queue that is missing the front element. /// </summary> /// <returns>A queue; never <c>null</c>.</returns> /// <exception cref="InvalidOperationException">Thrown when the queue is empty.</exception> public RealTimeQueue<T> Dequeue() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } return Create(_forwards.Pop(), _backwards, _lazy); } /// <summary> /// Retrieves the item at the head of the queue, and returns a queue with the head element removed. /// </summary> /// <param name="value">Receives the value from the head of the queue.</param> /// <returns>The new queue with the head element removed.</returns> /// <exception cref="InvalidOperationException">Thrown when the queue is empty.</exception> public RealTimeQueue<T> Dequeue(out T value) { value = this.Peek(); return this.Dequeue(); } /// <summary> /// Returns a queue that is missing the front element. /// </summary> /// <returns>A queue; never <c>null</c>.</returns> /// <exception cref="InvalidOperationException">Thrown when the queue is empty.</exception> IImmutableQueue<T> IImmutableQueue<T>.Dequeue() { return this.Dequeue(); } /// <summary> /// Returns an enumerator that iterates through the collection. /// </summary> /// <returns> /// An <see cref="Enumerator"/> that can be used to iterate through the collection. /// </returns> //public Enumerator GetEnumerator() //{ // return new Enumerator(this); //} /// <summary> /// Returns an enumerator that iterates through the collection. /// </summary> /// <returns> /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection. /// </returns> IEnumerator<T> IEnumerable<T>.GetEnumerator() { throw new NotImplementedException(); //return this.IsEmpty ? // Enumerable.Empty<T>().GetEnumerator() : // new EnumeratorObject(this); } /// <summary> /// Returns an enumerator that iterates through a collection. /// </summary> /// <returns> /// An <see cref="IEnumerator"/> object that can be used to iterate through the collection. /// </returns> IEnumerator IEnumerable.GetEnumerator() { throw new NotImplementedException(); //return new EnumeratorObject(this); } } public sealed partial class RealTimeQueue<T> { /// <summary> /// An immutable stack with lazy initialization. /// </summary> /// <typeparam name="T">The type of element stored by the stack.</typeparam> [DebuggerDisplay("IsEmpty = {IsEmpty}; Top = {_head}")] internal class LazyStack { /// <summary> /// The singleton empty stack. /// </summary> /// <remarks> /// Additional instances representing the empty stack may exist on deserialized stacks. /// </remarks> private static readonly LazyStack s_EmptyField = new LazyStack(); /// <summary> /// The element on the top of the stack. /// </summary> private T _head; /// <summary> /// A stack that contains the rest of the elements (under the top element). /// </summary> private LazyStack? _tail; /// <summary> /// A lazy initialization data. /// </summary> private LazyData? _lazy; /// <summary> /// Initializes a new instance of the <see cref="LazyStack{T}"/> class /// that acts as the empty stack. /// </summary> private LazyStack() { } /// <summary> /// Initializes a new instance of the <see cref="LazyStack{T}"/> class. /// </summary> /// <param name="head">The head element on the stack.</param> /// <param name="tail">The rest of the elements on the stack.</param> internal LazyStack(T head, LazyStack tail) { Debug.Assert(tail != null); _head = head; _tail = tail; } /// <summary> /// Initializes a new instance of the <see cref="LazyStack{T}"/> class with lazy initialization. /// </summary> internal LazyStack(LazyStack head, ImmutableStack<T> tail, LazyStack lazy) { _lazy = new LazyData(head, tail, lazy); } /// <summary> /// Gets the empty stack, upon which all stacks are built. /// </summary> public static LazyStack Empty { get { Debug.Assert(s_EmptyField.IsEmpty); return s_EmptyField; } } /// <summary> /// Gets the empty stack, upon which all stacks are built. /// </summary> public LazyStack Clear() { Debug.Assert(s_EmptyField.IsEmpty); return Empty; } /// <summary> /// Gets a value indicating whether this instance is empty. /// </summary> /// <value> /// <c>true</c> if this instance is empty; otherwise, <c>false</c>. /// </value> public bool IsEmpty { get { return _tail == null && _lazy == null; } } /// <summary> /// Gets the element on the top of the stack. /// </summary> /// <returns> /// The element on the top of the stack. /// </returns> /// <exception cref="InvalidOperationException">Thrown when the stack is empty.</exception> public T Peek() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } if (_tail == null && _lazy != null) { Evaluate(_lazy._heads, _lazy._tails, _lazy._lazy); } return _head!; } /// <summary> /// Gets a read-only reference to the element on the top of the stack. /// </summary> /// <returns> /// A read-only reference to the element on the top of the stack. /// </returns> /// <exception cref="InvalidOperationException">Thrown when the stack is empty.</exception> public ref readonly T PeekRef() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } if (_tail == null && _lazy != null) { Evaluate(_lazy._heads, _lazy._tails, _lazy._lazy); } return ref _head!; } /// <summary> /// Pushes an element onto a stack and returns the new stack. /// </summary> /// <param name="value">The element to push onto the stack.</param> /// <returns>The new stack.</returns> public LazyStack Push(T value) { return new LazyStack(value, this); } /// <summary> /// Returns a stack that lacks the top element on this stack. /// </summary> /// <returns>A stack; never <c>null</c></returns> /// <exception cref="InvalidOperationException">Thrown when the stack is empty.</exception> public LazyStack Pop() { if (this.IsEmpty) { throw new InvalidOperationException(SR.InvalidEmptyOperation); } if (_tail == null && _lazy != null) { Evaluate(_lazy._heads, _lazy._tails, _lazy._lazy); } Debug.Assert(_tail != null); return _tail; } /// <summary> /// Pops the top element off the stack. /// </summary> /// <param name="value">The value that was removed from the stack.</param> /// <returns> /// A stack; never <c>null</c> /// </returns> public LazyStack Pop(out T value) { if (_tail == null && _lazy != null) { Evaluate(_lazy._heads, _lazy._tails, _lazy._lazy); } value = this.Peek(); return this.Pop(); } internal void Evaluate(LazyStack heads, ImmutableStack<T> tails, LazyStack lazy) { if (heads.IsEmpty) { _head = tails.Peek(); _tail = lazy; } else { heads = heads.Pop(out _head); tails = tails.Pop(out T tailValue); _tail = new LazyStack(heads, tails, lazy.Push(tailValue)); } } private sealed class LazyData { public readonly LazyStack _heads; public readonly ImmutableStack<T> _tails; public readonly LazyStack _lazy; public LazyData(LazyStack heads, ImmutableStack<T> tails, LazyStack lazy) { _heads = heads; _tails = tails; _lazy = lazy; } } } } #region Expanded by https://github.com/naminodarie/SourceExpander //LICENSE: https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE #pragma warning disable namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}} namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}} namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public uint UInt{[MethodImpl(AggressiveInlining)]get=>(uint)ULong;}public uint UInt0{[MethodImpl(AggressiveInlining)]get=>UInt-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator uint(PropertyConsoleReader cr)=>cr.UInt;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}} namespace Kzrnm.Competitive{using static MethodImplOptions;public static class __ArrayExtension{[MethodImpl(AggressiveInlining)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[MethodImpl(AggressiveInlining)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[MethodImpl(AggressiveInlining)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[MethodImpl(AggressiveInlining)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[MethodImpl(AggressiveInlining)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length)return ref arr[index1][index2];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length&&(uint)index3<(uint)arr[index1][index2].Length)return ref arr[index1][index2][index3];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}}} internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){var sw=cw.StreamWriter;int Q=__ManyTestCases?cr.Int:1;for(;Q>0;Q--){var res=Calc();if(res is double d)sw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)sw.WriteLine(YesNo(b));else if(res is char[]chrs)sw.WriteLine(chrs);else if(res!=null&&res!=cw)sw.WriteLine(res.ToString());}cw.Flush();}} #endregion Expanded by https://github.com/naminodarie/SourceExpander