#1198991 (C#) No.3798 algo to goal

• 問題: No.3798 algo to goal
• ユーザー: tobisatis
• 提出日時: 2026-11-13 23:23:51
• 言語: C# (.NET 10.0.403 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,084 bytes
• コンパイル時間: 7,140 ms
• コンパイル使用メモリ: 173,372 KB
• 実行使用メモリ: 92,928 KB
• 最終ジャッジ日時: 2026-11-13 23:24:21
• 合計ジャッジ時間: 28,051 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 11 WA * 29

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (254 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

#nullable enable

using System.Numerics;

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

const int M = 26;

bool Solve()
{
    var s = I<string>().Select(e => e - 'a').ToArray();
    var t = I<string>().Select(e => e - 'a').ToArray();
    var n = s.Length;
    var (inv0, inv1) = (0L, 0L);
    for (var p = 0; p < 2; p++)
    {
        var cs = new int[M];
        var ct = new int[M];
        for (var i = p; i < n; i += 2) cs[s[i]]++;
        for (var i = p; i < n; i += 2) ct[t[i]]++;
        for (var i = 0; i < M; i++) if (cs[i] != ct[i]) return false;
        var a = new List<int>();
        var b = new List<int>();
        for (var i = p; i < n; i += 2) a.Add(s[i]);
        for (var i = p; i < n; i += 2) b.Add(t[i]);
        inv0 = FenwickTreeExtensions.InversionNumber(a, b) % 2;
        (inv0, inv1) = (inv1, inv0);
    }
    return inv0 == inv1;
}

var ans = new List<string>();
var q = I<int>();
while (q-- > 0) ans.Add(Solve() ? "Yes" : "No");
Console.WriteLine(string.Join(Environment.NewLine, ans));

class FenwickTree<T> where T :
    IAdditiveIdentity<T, T>,
    IAdditionOperators<T, T, T>,
    ISubtractionOperators<T, T, T>
{
    readonly T[] _values;

    public FenwickTree(int length)
    {
        var values = new T[length + 1];
        values.AsSpan().Fill(T.AdditiveIdentity);
        _values = values;
    }

    public FenwickTree(IReadOnlyList<T> data)
    {
        var values = new T[data.Count + 1];
        var span = values.AsSpan();
        for (var i = 1; i < span.Length; i++) span[i] = data[i - 1];
        for (var i = 1; i < span.Length; i++)
        {
            var j = i + (i & -i);
            if (j < span.Length) values[j] += values[i];
        }
        _values = values;
    }

    public void Add(int i, T value)
    {
        var values = _values.AsSpan();
        while (i < values.Length)
        {
            values[i] += value;
            i += i & -i;
        }
    }

    public T Sum(int i)
    {
        ReadOnlySpan<T> values = _values;
        var res = T.AdditiveIdentity;
        while (i > 0)
        {
            res += values[i];
            i -= i & -i;
        }
        return res;
    }
}

// [0..N)
class PointAddRangeSum<T> // : IRangeSum<T, PointAddRangeSum<T>>
    where T :
        IAdditiveIdentity<T, T>,
        IAdditionOperators<T, T, T>,
        ISubtractionOperators<T, T, T>
{
    readonly FenwickTree<T> _data;
    public PointAddRangeSum(int length) => _data = new(length);
    public PointAddRangeSum(IReadOnlyList<T> data) => _data = new(data);
    // public static PointAddRangeSum<T> Init(IReadOnlyList<T> data) => new(data);
    public void Add(int at, T value) => _data.Add(at + 1, value);
    public T Sum(int l, int r) => _data.Sum(r) - _data.Sum(l); // [l, r)
}

static class FenwickTreeExtensions
{
    // requires PointAddRangeSum
    public static long InversionNumber<T>(this IReadOnlyList<T> a, IReadOnlyList<T> target) where T : IComparable<T>
    {
        List<T> keys = [.. a, .. target];
        keys = [.. keys.Distinct().Order()];
        var n = keys.Count;
        if (n == 0) return 0;
        var sa = new Queue<int>[n];
        for (var i = 0; i < n; i++) sa[i] = [];
        for (var i = 0; i < a.Count; i++) sa[keys.BinarySearch(a[i])].Enqueue(i);
        var indices = new int[target.Count];
        for (var i = 0; i < target.Count; i++)
        {
            var q = sa[keys.BinarySearch(target[i])];
            if (q.Count == 0) return -1;
            indices[i] = q.Dequeue();
        }
        return indices.InversionNumber();
    }

    // shuffled [0..n)
    public static long InversionNumber(this int[] a)
    {
        var res = 0L;
        var n = a.Length;
        var data = new PointAddRangeSum<int>(n);
        foreach (var i in a)
        {
            res += data.Sum(i + 1, n);
            data.Add(i, 1);
        }
        return res;
    }

}