結果

問題 No.1017 Reiwa Sequence
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-03 23:13:05
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,935 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,830 ms
コンパイル使用メモリ 670,112 KB
実行使用メモリ 739,836 KB
最終ジャッジ日時 2026-11-03 23:14:44
合計ジャッジ時間 86,099 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40 TLE * 8 MLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.Bipartite;
import CPLib.Bits;
import CPLib.Convolution;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LDSegtree;
import CPLib.LSegtree;
import CPLib.MaxFlow;
// import CPLib.Memoize;
import CPLib.MinCostFlow;
import CPLib.Misc;
import CPLib.Monoid;
import CPLib.Segtree;
import CPLib.String;
import CPLib.Trait;
import CPLib.TwoSat;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

cM : I64 = 150000;

cI : I64 = (
    count_up(1).filter(|n|
        1.shift_left(n)-1 > cM*cM
    ).get_first.as_some
);

decode : I64 -> I64 -> Array I64 = |flag, len| (
    range(0, len).fold(([], flag), |_, (arr, flag)|
        let x = flag % 3;
        let r = if x == 0 { x } else if x == 1 { -1 } else { 1 };
        let arr = arr.push_back(r);
        let flag = flag / 3;
        (arr, flag)
    ).@0
);

sums : Array I64 -> HashMap I64 I64 = |as| (
    let len = as.@size;
    let pow3 = range(0, len).fold(1, |_, pow| pow * 3);
    let table = HashMap::empty(pow3);
    let table = range(0, pow3).fold(table, |flag, table|
        let bs = decode(flag, len);
        let sum = range(0, len).map(|i| as.@(i) * bs.@(i)).sum;
        table.HashMap::insert(sum, flag)
    );
    table
);

show_hashmap : HashMap I64 I64 -> String = |mp| (
    mp.to_iter.to_array.to_string
);

main : IO () = (
    let iN = *read_i;
    let iAs = *read_is(iN);
    let cL = min(cI, iN);
    let as = iAs.get_sub(0, cL);
    let mx = cM * as.@size;
    let dp = fill(2, fill(as.@size + 1, fill(2 * mx + 1, false)));
    let dp = dp[0][0][0 + mx].iset(true);
    let dp = range(0, as.@size).fold(dp, |n, dp|
        range(0, 2).fold(dp, |nz, dp|
            range(0, 2 * mx + 1).fold(dp, |sum_i, dp|
                if !dp[nz][n][sum_i].iget { dp };
                range(0, 3).fold(dp, |x_i, dp|
                    let x = x_i - 1;
                    let sum_i = sum_i + x * as.@(n);
                    let nz = nz == 1 || x != 0;
                    let nz = if nz { 1 } else { 0 };
                    dp[nz][n+1][sum_i].iset(true)
                )
            )
        )
    );
    if !dp[1][as.@size][mx].iget { println("No") };
    let (xs, _, _) = range_step(as.@size, 0, -1).fold(([], 1, mx), |n, (xs, nz, v)|
        // dp[nz][n][v] == true
        let a = as.@(n-1);
        let (prev_nz, x) = range(0, 2).product(range(0, 3)).map(|(prev_nz, x)| (prev_nz, x - 1)).filter(|(prev_nz, x)|
            dp[prev_nz][n-1][v + x * a].iget && (nz == 0 || prev_nz == 1 || x != 0)
        ).get_first.as_some;
        let prev_v = v + x * a;
        let xs = xs.push_back(x);
        (xs, prev_nz, prev_v)
    );
    let xs = xs.reverse;
    let ans = range(0, as.@size).map(|i| as.@(i) * xs.@(i)).to_array + fill(iN - as.@size, 0);
    println("Yes");;
    "{}".printfln((ans.to_iter.joined_with(" "),));;
    pure()
);
0