#1014311 (C#) No.1021 Children in Classrooms

• 問題: No.1021 Children in Classrooms
• ユーザー: RyotaKuji
• 提出日時: 2024-09-29 01:57:43
• 言語: C# (.NET 8.0.203)
• 結果: AC
• 実行時間: 148 ms / 2,000 ms
• コード長: 12,946 bytes
• コンパイル時間: 8,441 ms
• コンパイル使用メモリ: 166,736 KB
• 実行使用メモリ: 194,340 KB
• 最終ジャッジ日時: 2024-09-29 01:57:56
• 合計ジャッジ時間: 12,154 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	53 ms; 29,568 KB
testcase_01	AC	53 ms; 29,440 KB
testcase_02	AC	53 ms; 29,568 KB
testcase_03	AC	55 ms; 29,952 KB
testcase_04	AC	53 ms; 30,080 KB
testcase_05	AC	54 ms; 29,952 KB
testcase_06	AC	55 ms; 30,056 KB
testcase_07	AC	58 ms; 29,952 KB
testcase_08	AC	56 ms; 30,080 KB
testcase_09	AC	142 ms; 62,208 KB
testcase_10	AC	143 ms; 62,320 KB
testcase_11	AC	140 ms; 62,208 KB
testcase_12	AC	141 ms; 61,440 KB
testcase_13	AC	143 ms; 61,568 KB
testcase_14	AC	148 ms; 61,568 KB
testcase_15	AC	120 ms; 52,224 KB
testcase_16	AC	121 ms; 52,096 KB
testcase_17	AC	118 ms; 52,900 KB
testcase_18	AC	136 ms; 61,668 KB
testcase_19	AC	74 ms; 194,340 KB

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (97 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(399,34): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(403,35): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(253,21): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(255,21): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(252,14): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(254,11): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(170,28): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(254,13): warning CS0169: フィールド 'DictionarySort.currentString' は使用されていません [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/

ソースコード

namespace CSharp;

using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;
using static Output;
class _
{
    _()
    {
        Out("");
    }
}

public class Deque<T> : IEnumerator<T>, IEnumerable<T>,
                            IEnumerator, IEnumerable
{
    public int Count { get; private set; }

    T[] items = new T[16];
    int head;
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= Count)
            {
                throw new IndexOutOfRangeException(nameof(index));
            }
            return items[head + index];
        }
        set
        {
            if (index < 0 || index >= Count)
            {
                throw new IndexOutOfRangeException(nameof(index));
            }
            items[head + index] = value;
        }
    }
    public void PushBack(T item)
    {
        int index = head + Count;

        if (index == items.Length)
        {
            Resize();
            index = head + Count;
        }

        items[index] = item;
        Count++;
    }

    public void PushFront(T item)
    {
        if (head == 0)
        {
            Resize();
        }

        head--;
        items[head] = item;
        Count++;
    }

    public T PopBack()
    {
        if (Count == 0)
        {
            throw new InvalidOperationException();
        }

        T item = Back();
        Count--;

        if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        {
            items[head + Count] = default!;
        }

        return item;
    }

    public T PopFront()
    {
        if (Count == 0)
        {
            throw new InvalidOperationException();
        }

        T item = Front();
        Count--;
        head++;

        if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        {
            items[head] = default!;
        }

        return item;
    }

    public T Front() => items[head];
    public T Back() => items[head + Count - 1];

    void Resize()
    {
        int newCapacity = int.Clamp(items.Length * 2, 1, Array.MaxLength);
        int frontExtraCapacity = (newCapacity - Count) / 2;
        if (frontExtraCapacity == 0)
        {
            throw new("Array length over MaxLength");
        }
        T[] newArray = new T[newCapacity];
        Array.Copy(items, head, newArray, frontExtraCapacity, Count);
        items = newArray;
        head = frontExtraCapacity;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < Count; i++)
        {
            yield return this[i];
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        for (int i = 0; i < Count; i++)
        {
            yield return this[i];
        }
    }

    int enumeratorIndex = -1;
    public T Current => this[enumeratorIndex];

    object IEnumerator.Current => Current;

    public bool MoveNext()
    {
        enumeratorIndex++;
        return (enumeratorIndex <= Count);
    }

    public void Reset()
    {
        enumeratorIndex = -1;
    }

    bool disposedValue = false;
    public void Dispose()
    {
        Dispose(disposing: true);
        GC.SuppressFinalize(this);
    }
    protected virtual void Dispose(bool disposing)
    {
        if (disposedValue == false)
        {
            if (disposing)
            {
                // Dispose of managed resources.
            }
            foreach (var item in items)
            {
                IDisposable? disposableItem = items as IDisposable;
                if (disposableItem != null) disposableItem.Dispose();
            }
        }

        disposedValue = true;
    }

    ~Deque()
    {
        Dispose(disposing: false);
    }
}

class DictionarySort
{
    int[] originArray;
    int length => originArray.Length;
    public DictionarySort(List<int> list)
    {
        originArray = list.ToArray();
        Array.Sort(originArray);
    }

    public DictionarySort(string str)
    {
        originArray = new int[str.Length];
        for (int i = 0; i < length; i++)
        {
            originArray[i] = str[i];
        }
        Array.Sort(originArray);
    }

    public int[] GetArray(int n)
    {
        int[] result = new int[length];
        Stack<int> indexes = new();
        int tmpQuotient = n;
        for (int i = 1; i < length + 1; i++)
        {
            indexes.Push(tmpQuotient % i);
            tmpQuotient /= i;
        }
        indexes.Reverse();
        List<int> tmpList = new(originArray);
        for (int i = 0; i < length; i++)
        {
            int index = indexes.Pop();
            result[i] = tmpList[index];
            tmpList.RemoveAt(index);
        }
        return result;
    }
    public string GetString(int n)
    {
        return new(GetArray(n).Select(Convert.ToChar).ToArray());
    }

    public int GetOrder(List<int> list)
    {
        List<int> tmpList = new(this.originArray);
        int result = 0;
        int factorial = 1;
        for (int i = 1; i < list.Count; i++)
        {
            factorial *= i;
        }
        for (int i = 0; i < list.Count; i++)
        {
            int index = tmpList.FindIndex(x => x == list[i]);
            factorial /= (i + 1);
            result += factorial * index;
            tmpList.RemoveAt(index);
        }
        return result;
    }
    public int GetOrder(string str)
    {
        return GetOrder(str.Select(Convert.ToInt32).ToList());
    }

    List<int>? currentList;
    public List<int>? CurrentList => currentList;
    string? currentString;
    public List<int>? GetNextList()
    {
        if (currentList == null)
        {
            currentList = new(originArray);
        }
        else
        {
            if (Next(currentList) == false)
            {
                currentList = null;
            }
        }
        return currentList;
    }
    public static bool Next(List<int> list)
    {
        int changedIndex = -1;
        for (int i = 0; i < list.Count - 1; i++)
        {
            if (list[i] < list[i + 1])
            {
                changedIndex = i;
            }
        }

        if (changedIndex < 0) return false;

        int nextLarge = int.MaxValue;
        int nextLargeIndex = -1;
        for (int i = changedIndex + 1; i < list.Count; i++)
        {
            int item = list[i];
            if (item > list[changedIndex]
                && item < nextLarge)
            {
                nextLarge = item;
                nextLargeIndex = i;
            }
        }

        list[nextLargeIndex] = list[changedIndex];
        list[changedIndex] = nextLarge;
        List<int> rightRange = list.GetRange(changedIndex + 1, list.Count - changedIndex - 1);
        rightRange.Sort();
        for (int i = 0; i < rightRange.Count; i++)
        {
            list[i + changedIndex + 1] = rightRange[i];
        }

        return true;
    }
}
class Dijkstra
{
    readonly bool isDirected;
    List<List<(int to, int cost)>> edges;
    List<long> costs;
    bool executed = false;
    static readonly long INF = long.MaxValue;
    public Dijkstra(int vertexCount, bool? isDirected)
    {
        edges = new();
        costs = new();
        for (int i = 0; i < vertexCount; i++)
        {
            edges.Add(new());
            costs.Add(INF);
        }
        this.isDirected = isDirected ?? false;
    }
    public void Add(int from, int to, int cost)
    {
        edges[from].Add((to, cost));
        if (isDirected == false)
        {
            edges[to].Add((from, cost));
        }
    }
    public long GetCost(int vertex)
    {
        if (executed == false)
        {
            Execute();
        }
        return costs[vertex];
    }
    void Execute()
    {
        PriorityQueue<int, long> queue = new();
        queue.Enqueue(0, 0);
        while (queue.TryDequeue(out int edge, out long cost))
        {
            if (costs[edge] == INF)
            {
                costs[edge] = cost;
                foreach ((int to, long edgeCost) in edges[edge])
                {
                    if (costs[to] == INF)
                    {
                        queue.Enqueue(to, edgeCost + cost);
                    }
                }
            }
        }
    }
}
static class NumberSystem
{
    public static List<int> Convert(int deci, int numberSystem)
    {
        if (numberSystem <= 0)
        {
            throw new("Number system is invalid");
        }
        List<int> result = new();
        while (deci > 0)
        {
            result.Add(deci % numberSystem);
            deci /= numberSystem;
        }
        return result;
    }
}
static class Output
{
    public static StreamWriter StandardOutput = new(Console.OpenStandardOutput()) { AutoFlush = false };
    public static void YesNo(bool judge)
    {
        Out(judge, "Yes", "No");
    }
    public static void YESNO(bool judge)
    {
        Out(judge, "YES", "NO");
    }
    public static void yesno(bool judge)
    {
        Out(judge, "yes", "no");
    }
    public static void Out(bool judge, string yes, string no)
    {
        string result = judge ? yes : no;
        Out(result);
    }
    public static void Out(object? s = null)
    {
        Console.WriteLine(s);
    }
    public static void OutC(object? s = null)
    {
        Console.Write(s);
    }
}
class Palindrome
{
    public static bool IsPalindrome(string str)
    {
        for (int i = 0; i < str.Length / 2; i++)
        {
            if (str[i] != str[str.Length - i - 1])
            {
                return false;
            }
        }
        return true;
    }
}
static class Scan
{
    static string[] s;
    static int i;
    static char[] cs = new char[] { ' ' };
    public static string Path = "";
    static Scan()
    {
        s = new string[0];
        i = 0;
    }
    public static string Str()
    {
        if (i < s.Length) return s[i++];
        string st;
        if (File.Exists(Path))
        {
            st = File.ReadAllText(Path);
            Regex whiteSpaceRegex = new(@"\s+");
            st = whiteSpaceRegex.Replace(st, " ").Trim();
        }
        else
        {
            st = Console.ReadLine();
        }
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Str();
        i = 0;
        return s[i++];
    }

    public static int Int() => int.Parse(Str());
    public static long Long() => long.Parse(Str());
    public static double Double() => double.Parse(Str());
}
class UnionFind
{
    List<int> parent;
    List<int> size;
    public UnionFind(int nodeCount)
    {
        parent = new();
        size = new();
        for (int i = 0; i < nodeCount; i++)
        {
            parent.Add(i);
            size.Add(1);
        }
    }

    public int Root(int x)
    {
        if (parent[x] == x)
        {
            return x;
        }
        parent[x] = Root(parent[x]);
        return parent[x];
    }

    public void Union(int x, int y)
    {
        int rootX = Root(x);
        int rootY = Root(y);
        if (rootX != rootY)
        {
            if (Size(rootX) < Size(rootY))
            {
                (rootX, rootY) = (rootY, rootX);
            }
            size[rootX] += size[rootY];
            parent[rootY] = rootX;
        }
    }

    public int Size(int x)
    {
        int root = Root(x);
        return size[root];
    }

    public bool IsConnected()
    {
        int root = Root(0);
        for (int i = 0; i < parent.Count; i++)
        {
            if (Root(i) != root)
            {
                return false;
            }
        }
        return true;
    }
}


class Program
{
    public static Action StaticSolve => new Program().Solve;
    [STAThread]
    static void Main()
    {
        Console.OutputEncoding = Encoding.UTF8;
        Console.SetOut(StandardOutput);
#if DEBUG
        Service.Input();
#else
		StaticSolve();
#endif
        Console.Out.Flush();
    }


    // long MOD = (long)Math.Pow(10, 9) + 7;
    // long MOD = (long)Math.Pow(10, 9) + 9;
    // (int r, int c)[] incrs = { (-1, 0), (0, 1), (1, 0), (0, -1) };

    public void Solve()
    {
        int n = Scan.Int();
        int m = Scan.Int();
        Deque<int> deq = new();
        for (int i = 0; i < n; i++)
        {
            deq.PushBack(Scan.Int());
        }
        string s = Scan.Str();
        foreach (char c in s)
        {
            if (c == 'L')
            {
                int value = deq.PopFront();
                value += deq.PopFront();
                deq.PushFront(value);
                deq.PushBack(0);
            }
            else
            {
                int value = deq.PopBack() + deq.PopBack();
                deq.PushBack(value);
                deq.PushFront(0);
            }
        }
        foreach (var item in deq)
        {
            OutC(item+" ");
        }
    }
}