結果

問題 No.3565 Take from Excluded
コンテスト
ユーザー kakel-san
提出日時 2026-06-05 22:06:24
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
WA  
実行時間 -
コード長 3,839 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 19,195 ms
コンパイル使用メモリ 177,588 KB
実行使用メモリ 65,152 KB
最終ジャッジ日時 2026-06-05 22:06:55
合計ジャッジ時間 19,646 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (93 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

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]);
        if (n > 3000 || q > 3000)
        {
            WriteLine(-1);
            return;
        }
        var a = NList;
        var map = NArr(q);
        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 % 2 == 1)
            {
                list = Shift(Next(list, m), (k - 1) / 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;
            }
        }
        WriteLine(string.Join("\n", 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;
    }
}
0