結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー kakel-san
提出日時 2025-10-31 22:32:54
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,174 ms / 2,000 ms
コード長 3,552 bytes
コンパイル時間 10,849 ms
コンパイル使用メモリ 172,344 KB
実行使用メモリ 223,396 KB
最終ジャッジ日時 2025-11-01 10:01:14
合計ジャッジ時間 47,427 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (134 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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

class Program
{
    static int NN => int.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    static long[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        nlist[0] = 1;
        blist[0] = 1;
        for (var i = 1; i < nlist.Length; ++i)
        {
            nlist[i] = nlist[i - 1] + blist[i - 1] * 5;
            blist[i] = blist[i - 1] * 2;
        }
        var c = NList;
        var (n, q) = ((int)c[0], (int)c[1]);
        var s = ReadLine();
        var query = NArr(q);
        var list = new List<(int id, long t, long x)>(q);
        for (var i = 0; i < q; ++i) list.Add((i, query[i][0], query[i][1]));
        list.Sort((l, r) => l.t.CompareTo(r.t));

        var pos = new long[n + 1];
        var ans = new char[q];
        for (var i = 0; i < q; ++i)
        {
            var t = (int)Math.Min(list[i].t, nlist.Length - 1);
            var x = list[i].x - 1;
            if (i == 0 || (list[i - 1].t < t && list[i - 1].t < nlist.Length))
            {
                for (var j = 0; j < n; ++j)
                {
                    if (s[j] == 'a' || s[j] == 'w') pos[j + 1] = pos[j] + nlist[t];
                    else pos[j + 1] = pos[j] + 1;
                    if (pos[j + 1] > INF) pos[j + 1] = INF;
                }
            }
            // WriteLine($"pos = {string.Join(" ", pos)}");
            var lb = LowerBound(0, x, pos);
            if (x < pos[lb]) --lb;
            // WriteLine($"x = {x}, lb = {lb}");
            if (s[lb] == 'a')
            {
                ans[list[i].id] = DFS("answer", x - pos[lb], t - 1);
            }
            else if (s[lb] == 'w')
            {
                ans[list[i].id] = DFS("warong", x - pos[lb], t - 1);
            }
            else
            {
                ans[list[i].id] = s[lb];
            }
        }
        WriteLine(string.Concat(ans));
    }
    static long INF = long.MaxValue / 2;
    static long[] nlist = new long[59];
    static long[] blist = new long[59];
    static char DFS(string s, long pos, int dep)
    {
        var plist = new long[7];
        for (var i = 0; i < 6; ++i)
        {
            if (s[i] == 'a' || s[i] == 'w') plist[i + 1] = plist[i] + nlist[dep];
            else plist[i + 1] = plist[i] + 1;
            if (plist[i + 1] > INF) plist[i + 1] = INF;
        }
        // WriteLine($"pos = {string.Join(" ", plist)}");
        // WriteLine($"search {pos}");
        for (var i = 0; i < 6; ++i)
        {
            if (plist[i] == pos)
            {
                return s[i];
            }
            else if (plist[i] < pos && pos < plist[i + 1])
            {
                if (s[i] == 'a') return DFS("answer", pos - plist[i], dep - 1);
                else return DFS("warong", pos - plist[i], dep - 1);
            }
        }
        return ' ';
    }
    static int LowerBound(int left, long min, IList<long> list)
    {
        if (list[left] >= min) return left;
        var ng = left;
        var ok = list.Count;
        while (ok - ng > 1)
        {
            var mid = (ng + ok) / 2;
            if (list[mid] < min) ng = mid;
            else ok = mid;
        }
        return ok;
    }
}
0