結果

問題 No.9 モンスターのレベル上げ
ユーザー くれちー
提出日時 2018-02-01 20:40:43
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 3,002 ms / 5,000 ms
コード長 4,783 bytes
コンパイル時間 1,431 ms
コンパイル使用メモリ 119,472 KB
実行使用メモリ 26,852 KB
最終ジャッジ日時 2024-06-24 00:24:12
合計ジャッジ時間 21,918 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using static System.Math;
using static Extensions;

public static class Program
{
    public static void Solve()
    {
        var n = I;
        var a = Repeat(n, () => I).ToArray();
        var b = Repeat(n, () => I).ToArray();
        var pq = new BinaryHeap<(int, int)>();
        var min = int.MaxValue;

        Repeat(n, i =>
        {
            var max = 0;
            a.ForEach(x => pq.Enqueue((x, 0)));
            Repeat(n, j =>
            {
                j = (i + j >= n) ? (i + j - n) : (i + j);
                var (x, y) = pq.Dequeue();
                max = Max(max, y + 1);
                pq.Enqueue((x + b[j] / 2, y + 1));
            });
            pq.Clear();
            min = Min(min, max);
        });

        Answer(min);
    }

    static TextScanner _ts;
    static int I => int.Parse(_ts.Next());

    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput());
        sw.NewLine = "\n";
#if DEBUG
        sw.AutoFlush = true;
#else
        sw.AutoFlush = false;
#endif
        Console.SetOut(sw);
        _ts = new TextScanner(Console.In);
        Solve();
        Console.Out.Flush();
    }
}

#region Library
#pragma warning disable
public interface IPriorityQueue<T>
{
    int Count { get; }
    bool Any();
    void Clear();
    void Enqueue(T item);
    T Dequeue();
    T Peek();
}

public class BinaryHeap<T> : IPriorityQueue<T>
{
    private readonly IComparer<T> _comparer;
    private readonly List<T> _t;

    public BinaryHeap() : this(Comparer<T>.Default) { }

    public BinaryHeap(IComparer<T> comparer)
    {
        _t = new List<T>();
        _comparer = comparer;
    }

    public BinaryHeap(int capacity) : this(capacity, Comparer<T>.Default) { }

    public BinaryHeap(int capacity, IComparer<T> comparer)
    {
        _t = new List<T>(capacity);
        _comparer = comparer;
    }

    public int Count { get; private set; }

    public int Capacity => _t.Capacity;

    public bool Any() => this.Count > 0;

    public void Clear()
    {
        _t.Clear();
        this.Count = 0;
    }

    public void TrimExcess() => _t.TrimExcess();

    public void Enqueue(T item)
    {
        var i = this.Count++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (_comparer.Compare(_t[p], item) <= 0) break;
            Set(i, _t[p]);
            i = p;
        }
        Set(i, item);
    }

    public T Dequeue()
    {
        if (this.Count == 0) throw new InvalidOperationException();
        var ret = _t[0];
        var x = _t[--this.Count];
        var i = 0;
        while ((i << 1) + 1 < this.Count)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < this.Count && _comparer.Compare(_t[b], _t[a]) < 0) a = b;
            if (_comparer.Compare(_t[a], x) >= 0) break;
            _t[i] = _t[a];
            i = a;
        }
        _t[i] = x;
        return ret;
    }

    public T Peek()
    {
        if (this.Count == 0) throw new InvalidOperationException();
        return _t[0];
    }

    private void Set(int i, T value)
    {
        if (i < _t.Count) _t[i] = value;
        else if (i == _t.Count) _t.Add(value);
        else throw new InvalidOperationException();
    }
}

public class TextScanner
{
    private readonly TextReader _tr;

    public TextScanner(TextReader tr)
    {
        _tr = tr;
    }

    public string Next()
    {
        var sb = new StringBuilder();
        int i;
        do
        {
            i = _tr.Read();
            if (i == -1) throw new EndOfStreamException();
        }
        while (char.IsWhiteSpace((char)i));
        while (i != -1 && !char.IsWhiteSpace((char)i))
        {
            sb.Append((char)i);
            i = _tr.Read();
        }
        return sb.ToString();
    }
}

public static class Constants
{
}

[DebuggerStepThrough]
public static partial class Extensions
{
    public static void Answer(object value)
    {
        Console.WriteLine(value);
        Exit(0);
    }

    public static void Exit(int exitCode)
    {
        Console.Out.Flush();
        Environment.Exit(exitCode);
    }

    public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
    {
        foreach (var item in source) action(item);
    }

    public static void Repeat(int count, Action<int> action)
    {
        for (var i = 0; i < count; i++) action(i);
    }

    public static IEnumerable<T> Repeat<T>(int count, Func<T> func)
    {
        for (var i = 0; i < count; i++) yield return func();
    }
}

[DebuggerStepThrough]
public static class MathExtensions
{
}
#pragma warning restore
#endregion
0