結果

問題 No.3041 非対称じゃんけん
コンテスト
ユーザー kakel-san
提出日時 2025-03-01 02:04:23
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 3,679 bytes
コンパイル時間 8,434 ms
コンパイル使用メモリ 170,704 KB
実行使用メモリ 58,868 KB
最終ジャッジ日時 2025-03-01 02:04:54
合計ジャッジ時間 20,671 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 6 WA * 18 TLE * 2 -- * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (114 ミリ秒)。
  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;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var p = NList;
        var (n, f) = (p[0], p[1]);
        var a = NList;
        var b = NList;
        var c = NList;
        var len = n * f + 61;
        var s = new Bitset(len);
        s.Set(0, true);
        var ans = new int[n];
        for (var i = 0; i < n; ++i)
        {
            var sa = s.Clone();
            sa.LShift(a[i]);
            var sb = s.Clone();
            sb.LShift(b[i]);
            var sc = s.Clone();
            sc.LShift(c[i]);
            sa.Or(sb);
            sa.Or(sc);
            ans[i] = sa.Popcount();
            s = sa;
        }
        WriteLine(string.Join("\n", ans));
    }
    class Bitset
    {
        int _length;
        ulong[] data;
        public Bitset(int length)
        {
            _length = length;
            data = new ulong[(length + 63) / 64];
        }
        public void Set(int pos, bool val)
        {
            if (!val) data[pos / 64] = data[pos / 64] & (ulong.MaxValue ^ ((ulong)1 << (pos % 64)));
            else data[pos / 64] = data[pos / 64] | ((ulong)1 << (pos % 64));
        }
        public void Or(Bitset b)
        {
            for (var i = 0; i < data.Length; ++i) data[i] = data[i] | b.data[i];
        }
        public bool Includes(Bitset b)
        {
            for (var i = 0; i < data.Length; ++i) if ((data[i] | b.data[i]) != data[i]) return false;
            return true;
        }
        public bool Equals(Bitset b)
        {
            for (var i = 0; i < data.Length; ++i) if (data[i] != b.data[i]) return false;
            return true;
        }
        public bool[] Expand()
        {
            var ans = new bool[_length];
            for (var i = 0; i < _length; ++i) ans[i] = (data[i / 64] >> (i % 64)) % 2 == 1;
            return ans;
        }
        public Bitset Clone()
        {
            var nb = new Bitset(_length);
            for (var i = 0; i < data.Length; ++i) nb.data[i] = data[i];
            return nb;
        }
        /// <summary>全体の値に対して左シフトを行う はみ出た値は削除される</summary>
        /// <param name="len">シフトする長さ (0～64)</param>
        public void LShift(int len)
        {
            for (var i = data.Length - 1; i >= 0; --i)
            {
                if (i > 0) data[i] = (data[i] << len) | (data[i - 1] >> 64 - len);
                else data[i] <<= len;
            }
        }
        public override string ToString()
        {
            return string.Join(" ", Expand().Select(f => f ? "o" : "x"));
        }
        public int Popcount()
        {
            var ans = 0;
            for (var i = 0; i < data.Length; ++i) ans += Popcount(data[i]);
            return ans;
        }
        int Popcount(ulong n)
        {
            var c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555);
            c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333);
            c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f);
            c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff);
            c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff);
            c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff);
            return (int)c;
        }
    }
}
0