#1168336 (C#) No.3565 Take from Excluded

• 問題: No.3565 Take from Excluded
• ユーザー: kakel-san
• 提出日時: 2026-06-05 22:20:00
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 1,006 ms / 2,000 ms
• コード長: 4,113 bytes
• コンパイル時間: 14,446 ms
• コンパイル使用メモリ: 175,396 KB
• 実行使用メモリ: 65,280 KB
• 最終ジャッジ日時: 2026-06-05 22:20:31
• 合計ジャッジ時間: 19,598 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 2
other	AC * 14 WA * 4

コンパイルメッセージ

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

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, q) = (c[0], c[1]);
        var a = NList;
        var map = NArr(q);
        if (n > 3000 || q > 3000)
        {
            WriteLine(-1);
            return;
        }
        WriteLine(string.Join("\n", Ext(n, q, a, map)));
    }
    static long[] Ext(int n, int q, int[] a, int[][] map)
    {
        var list = Create(a);
        var ans = new long[q];
        for (var i = 0; i < q; ++i)
        {
            var k = map[i][0];
            var x = map[i][1] - 1;
            var m = map[i][2];
            if (k == 1)
            {
                list = Next(list, m);
                ans[i] = Get(list, x);
            }
            else if (k == 2)
            {
                list = Next(Next(list, m), m);
                ans[i] = Get(list, x);
            }
            else if (k == 3)
            {
                list = Next(Next(Next(list, m), m), m);
                ans[i] = Get(list, x);
            }
            else if (k % 2 == 1)
            {
                list = Shift(Next(Next(Next(list, m), m), m), (k - 3) / 2, m);
                ans[i] = Get(list, x) % mod;
            }
            else
            {
                list = Shift(Next(Next(list, m), m), (k - 2) / 2, m);
                ans[i] = Get(list, x) % mod;
            }
        }
        return ans;
    }
    class Range
    {
        public long Min;
        public long Max;
        public Range(long min, long max)
        {
            Min = min; Max = max;
        }
    }
    static List<Range> Create(int[] a)
    {
        var set = new HashSet<int>(a);
        var list = new List<int>(set);
        list.Sort();
        var ans = new List<Range>{ new Range(list[0], list[0] )};
        for (var i = 1; i < list.Count; ++i)
        {
            if (list[i] - list[i - 1] > 1)
            {
                ans[^1].Max = list[i - 1];
                ans.Add(new Range(list[i], list[i]));
            }
            ans[^1].Max = list[i];
        }
        return ans;
    }
    static int mod = 998_244_353;
    static List<Range> Next(List<Range> cur, int m)
    {
        var rest = (long)m;
        var ans = new List<Range>();
        for (var i = 0; i + 1 < cur.Count; ++i)
        {
            var min = cur[i].Max + 1;
            var max = Math.Min(min + rest - 1, cur[i + 1].Min - 1);
            ans.Add(new Range(min, max));
            rest -= max - min + 1;
            if (rest <= 0) break;
        }
        if (rest > 0)
        {
            var min = cur[^1].Max + 1;
            ans.Add(new Range(min, min + rest - 1));
        }
        var rem = ans[0].Min - ans[0].Min % mod;
        for (var i = 0; i < ans.Count; ++i) ans[i] = new Range(ans[i].Min - rem, ans[i].Max - rem);
        return ans;
    }
    static List<Range> Shift(List<Range> cur, int k, int m)
    {
        var loop = k / cur.Count;
        var shift = k % cur.Count;
        var ans = new List<Range>();
        var add = (long)loop * m * 2;
        for (var i = shift; i < cur.Count; ++i) ans.Add(new Range(cur[i].Min + add, cur[i].Max + add));
        for (var i = 0; i < shift; ++i) ans.Add(new Range(cur[i].Min + add + m * 2, cur[i].Max + add + m * 2));
        var rem = ans[0].Min - ans[0].Min % mod;
        for (var i = 0; i < ans.Count; ++i) ans[i] = new Range(ans[i].Min - rem, ans[i].Max - rem);
        return ans;
    }
    static long Get(List<Range> cur, int x)
    {
        var rest = (long)x;
        foreach (var ci in cur)
        {
            var count = ci.Max - ci.Min + 1;
            if (rest < count)
            {
                return ci.Min + rest;
            }
            rest -= count;
        }
        return -1;
    }
}