結果

問題 No.3047 Verification of Sorting Network
ユーザー 👑 Mizar
提出日時 2025-01-16 00:48:14
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 4,060 bytes
コンパイル時間 17,725 ms
コンパイル使用メモリ 172,332 KB
実行使用メモリ 224,428 KB
最終ジャッジ日時 2025-03-05 20:31:19
合計ジャッジ時間 41,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (114 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

const int MAX_T = 10000;
const int MAX_N = 27;
const double MAX_COST = 1e8;

var t = int.Parse(Console.ReadLine());
if (t > MAX_T) throw new ArgumentException($"t must be <= {MAX_T}");

var phi = Math.Sqrt(1.25) + 0.5;
double cost = 0.0;

for (int i = 0; i < t; i++)
{
    var input = Console.ReadLine().Split();
    var n = int.Parse(input[0]);
    var m = int.Parse(input[1]);
    var cmps = new List<(int, int)>();
    if (n < 2 || n > MAX_N || m < 1 || m > n * (n - 1) / 2) throw new ArgumentException("Invalid input");
    cost += m * Math.Pow(phi, n);
    int[] va = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int[] vb = Console.ReadLine().Split().Select(int.Parse).ToArray();
    if (va.Length != m || vb.Length != m) throw new InvalidDataException("Invalid data length");
    for (int j = 0; j < m; j++)
    {
        if (!(1 <= va[j] && va[j] < vb[j] && vb[j] <= n)) throw new ArgumentException("Invalid input");
        cmps.Add((va[j] - 1, vb[j] - 1));
    }
    var result = IsSortingNetwork(n, cmps.ToArray());
    Console.WriteLine(result.to_string);
    if (result.is_ok)
    {
        if (result.data.Length != m) throw new InvalidDataException("Invalid unused_cmp data length");
    }
    else
    {
        if (result.data.Length != n - 1) throw new InvalidDataException("Invalid unsorted_node data length");
    }
    var index = result.data.AsEnumerable().Select((k, i) => (k, i)).Where(x => x.k).Select(x => x.i).ToArray();
    Console.WriteLine(index.Length);
    Console.WriteLine(string.Join(" ", index.AsEnumerable().Select(k => k + 1)));
}
if (cost > MAX_COST) throw new ArgumentException("Cost exceeds limit");

static Result<bool[]> IsSortingNetwork(int n, (int, int)[] cmps)
{
    var stack = new Stack<(int, State[], int, int)>(n);
    stack.Push((0, Enumerable.Range(0, n).Select(i => State.Unknown).ToArray(), 0, n - 1));
    bool[] unused = Enumerable.Repeat(true, cmps.Length).ToArray();
    bool[] unsorted = new bool[n - 1];

    while (stack.Count > 0)
    {
        var (i, p, z, o) = stack.Pop();
        while (i < cmps.Length)
        {
            var (a, b) = cmps[i++];
            if (p[a] == State.Unknown && p[b] == State.Unknown)
            {
                unused[i - 1] = false;
                State[] q = (State[])p.Clone();
                q[a] = q[b] = State.Zero;
                p[b] = State.One;
                for (var j = z; j < o; j++)
                {
                    if (p[j] != State.Zero)
                    {
                        stack.Push((i, q, j, o));
                        break;
                    }
                }
                while (p[o] == State.One)
                {
                    o--;
                    if (z >= o)
                    {
                        goto A;
                    }
                }
            }
            else if (p[a] != State.Zero && p[b] != State.One)
            {
                unused[i - 1] = false;
                (p[a], p[b]) = (p[b], p[a]);
                while (p[z] == State.Zero)
                {
                    z++;
                    if (z >= o)
                    {
                        goto A;
                    }
                }
                while (p[o] == State.One)
                {
                    o--;
                    if (z >= o)
                    {
                        goto A;
                    }
                }
            }
        }
        for (int j = 0; j < n - 1; ++j)
        {
            if (p[j] != State.Zero && p[j + 1] != State.One)
            {
                unsorted[j] = true;
            }
        }
    A:;
    }
    if (unsorted.Any(u => u))
    {
        return new Result<bool[]>(false, unsorted);
    }
    return new Result<bool[]>(true, unused);
}

enum State
{
    Zero,
    One,
    Unknown
}

class Result<T>
{
    public bool is_ok;
    public T data;
    public string to_string => is_ok ? "Yes" : "No";
    public Result(bool is_ok, T data)
    {
        this.is_ok = is_ok;
        this.data = data;
    }
}
0