結果

問題 No.689 E869120 and Constructing Array 3
コンテスト
ユーザー 👑 kakel-san
提出日時 2026-10-19 02:17:41
言語 C#
(.NET 10.0.402 + ACL)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 48 ms / 1,000 ms
+ 768µs
コード長 2,509 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,373 ms
コンパイル使用メモリ 169,572 KB
実行使用メモリ 34,560 KB
最終ジャッジ日時 2026-10-19 02:17:51
合計ジャッジ時間 8,846 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge6_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (170 ミリ秒)。
  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();
    public static void Main()
    {
        IsPrime = new bool[1_000_000];
        for (var i = 2; i < IsPrime.Length; ++i) IsPrime[i] = true;
        for (var i = 2; i < IsPrime.Length; ++i)
        {
            if (IsPrime[i])
            {
                for (var j = i * 2; j < IsPrime.Length; j += i) IsPrime[j] = false;
            }
        }
        var k = NN;
        if (k == 0)
        {
            WriteLine(1);
            WriteLine(1);
            return;
        }
        var ans = Calc(k);
        WriteLine(ans.Count);
        WriteLine(string.Join(" ", ans));
    }
    static bool[] IsPrime;
    static List<int> Calc(int k)
    {
        var r = new Random();
        var ans = new List<int>();
        var even = new HashSet<int>();
        var odd = new HashSet<int>();
        var rest = k;
        while (rest > 0)
        {
            var (e, o, ec, oc) = AddPair(r, rest, even, odd);
            for (var i = 0; i < ec; ++i) ans.Add(e);
            for (var i = 0; i < oc; ++i) ans.Add(o);
            even.Add(e);
            odd.Add(o);
            rest -= ec * oc;
        }
        return ans;
    }
    static (int e, int o, int ec, int oc) AddPair(Random r, int rest, HashSet<int> even, HashSet<int> odd)
    {
        var count = 0;
        for (var i = 1; ; ++i)
        {
            if ((i == 1 && rest < 3) || (i - 1) * (i - 1) < rest && i * i >= rest)
            {
                count = i;
                break;
            }
        }
        var ec = count;
        var oc = count;
        for (var d = 0; d < count; ++d)
        {
            if (count * count - d * d <= rest)
            {
                ec = count + d;
                oc = count - d;
                break;
            }
        }
        while (true)
        {
            var e1 = r.Next(1000, 200000) * 2;
            var o1 = r.Next(1000, 200000) * 2 + 1;
            if (IsPrime[e1 + o1])
            {
                var flg = true;
                foreach (var e in even) if (IsPrime[e + o1]) flg = false;
                foreach (var o in odd) if (IsPrime[o + e1]) flg = false;
                if (flg) return (e1, o1, ec, oc);
            }
        }
    }
}
0