結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー tobisatis
提出日時 2025-02-25 21:36:52
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,780 ms / 2,000 ms
コード長 4,003 bytes
コンパイル時間 17,903 ms
コンパイル使用メモリ 173,260 KB
実行使用メモリ 200,928 KB
スコア 1,910,424
最終ジャッジ日時 2025-02-25 21:38:43
合計ジャッジ時間 110,585 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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/

ソースコード

diff # 

#nullable enable

using System.Numerics;

const int Mod = 100000000;
const int n = 50;
const int l = (n * (n + 1)) >> 1;
const int cc = 50;
var random = new Random(1);

const int tl = 1700;
var sw = new System.Diagnostics.Stopwatch();
bool TL() => sw.ElapsedMilliseconds < tl;

void Run()
{
    Int();
    var py = (stackalloc int[l]);
    {
        var k = 0;
        for (var i = 0; i < n; i++) for (var j = 0; j <= i; j++) py[k++] = Int();
    }
    sw.Start();
    static int I(int i, int j) => ((i * (i + 1)) >> 1) + j;
    static int AV(int i, int j, Span<int> py) => py[I(i, j)];
    var qy = (stackalloc int[cc * l]);
    for (var i = 0; i < qy.Length; i++) qy[i] = random.Next(Mod);
    static int E(int c, Span<int> py, Span<int> sy)
    {
        var ge = -1;
        for (var i = 0; i < n; i++) for (var j = 0; j <= i; j++)
        {
            var d = Math.Abs(AV(i, j, py) - sy[I(i, j)]);
            var e = Math.Min(d, Mod - d);
            if (e > ge) ge = e;
        }
        return ge;
    }
    static void TryC(int c, Random random, Span<int> py, Span<int> qy)
    {
        var li = l * c;
        var oy = (stackalloc int[l]);
        qy.Slice(li, l).CopyTo(oy);
        var ny = (stackalloc int[l]);
        oy.CopyTo(ny);
        var ge = E(c, py, oy);
        var i = random.Next(n);
        var r = random.Next(ge) - (ge >> 1);
        if (r >= 0) r++;
        ny[l - n + i] += r;
        if (ny[l - n + i] >= Mod) ny[l - n + i] -= Mod;
        if (ny[l - n + i] < 0) ny[l - n + i] += Mod;
        var cl = i;
        var cr = i + 1;
        for (var level = n - 2; level >= 0; level--)
        {
            cl = Math.Max(0, cl - 1);
            cr = Math.Min(level + 1, cr + 1);
            for (var j = cl; j < cr; j++)
            {
                var di = I(level + 1, j);
                var nv = (ny[di] + ny[di + 1]) % Mod;
                ny[I(level, j)] = nv;
            }
        }
        var ne = E(c, py, ny);
        if (ne < ge) for (var j = 0; j < l; j++) qy[li++] = ny[j];
    }
    while (TL())
    {
        for (var c = 0; c < cc; c++) TryC(c, random, py, qy);
    }
    var (be, bc) = (Mod, -1);
    for (var i = 0; i < cc; i++)
    {
        var e = E(i, py, qy.Slice(l * i, l));
        if (e < be)
        {
            be = e;
            bc = i;
        }
    }
    Out(qy.Slice(l * bc + l - n, n).ToArray(), " ");
}

#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
{
//     static readonly StreamReader _sr = new("input.txt");
//     static readonly StreamWriter _sw = new("output.txt", false);
    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();
}
0