結果

問題 No.1209 XOR Into You
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-11 22:16:10
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 1,192 ms / 2,000 ms
+ 33µs
コード長 2,104 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,322 ms
コンパイル使用メモリ 679,740 KB
実行使用メモリ 18,236 KB
最終ジャッジ日時 2026-11-11 22:16:58
合計ジャッジ時間 22,956 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import CPLib.IO;
import CPLib.Monoid::Sum;
import CPLib.Segtree;

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

main : IO () = (
    let n = *read_i;
    let as = *read_is(n);
    let bs = *read_is(n);
    if as.@(0) != bs.@(0) {
        println("-1")
    };
    let as = range(1,n).fold([], |i, acm| let v = as.@(i-1).bit_xor(as.@(i)); acm.push_back(v));
    let bs = range(1,n).fold([], |i, acm| let v = bs.@(i-1).bit_xor(bs.@(i)); acm.push_back(v));
    if as.sort != bs.sort {
        println("-1")
    };
    let n = n - 1;
    let mp = HashMap::empty(n);
    let mp = range_step(n-1, -1, -1).fold(mp, |i, mp|
        let a = as.@(i);
        // HashMapユーティリティーがほしい
        match mp.find(a) {
            none() => mp.insert(a, [i]),
            some(ls) => mp.insert(a, ls.push_back(i))
        }
    );
    // xs[i] = 移動後にi番目にくるべき数は最初はどこにいたか。
    let (xs, _) = range(0, n).fold(([], mp), |i, (xs, mp)|
        let b = bs.@(i);
        let ls = mp.find(b).as_some; // HashMapの身代わりパターンが面倒
        let mp = mp.insert(b, []);
        let i = ls.@(ls.@size-1);
        let xs = xs.push_back(i);
        let ls = ls.pop_back;
        let mp = mp.insert(b, ls);
        (xs, mp)
    );
    let tree = Segtree::create(n) : Segtree (Sum I64);
    let (_, ans) = range(0, n).fold((tree, 0), |i, (tree, ans)|
        let move = xs.@(i) - i + tree.fold(xs.@(i)+1, n).@v;
        let ans = ans + move;
        let tree = tree.set(xs.@(i), Sum {v: 1});
        (tree, ans)
    );
    ans.to_string.println;;
    pure()
);
0