結果

問題 No.2672 Subset Xor Sum
ユーザー tktk_snsntktk_snsn
提出日時 2024-04-07 00:11:43
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 5,800 bytes
コンパイル時間 12,315 ms
コンパイル使用メモリ 170,404 KB
実行使用メモリ 187,184 KB
最終ジャッジ日時 2024-10-01 04:10:03
合計ジャッジ時間 12,990 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
29,056 KB
testcase_01 AC 49 ms
29,312 KB
testcase_02 AC 49 ms
29,440 KB
testcase_03 AC 49 ms
29,568 KB
testcase_04 AC 50 ms
29,180 KB
testcase_05 AC 49 ms
29,440 KB
testcase_06 AC 49 ms
29,312 KB
testcase_07 AC 48 ms
29,312 KB
testcase_08 AC 49 ms
29,440 KB
testcase_09 AC 48 ms
29,312 KB
testcase_10 AC 47 ms
29,312 KB
testcase_11 AC 48 ms
29,696 KB
testcase_12 AC 48 ms
29,440 KB
testcase_13 AC 47 ms
29,696 KB
testcase_14 AC 51 ms
29,440 KB
testcase_15 AC 52 ms
29,312 KB
testcase_16 AC 52 ms
29,312 KB
testcase_17 AC 49 ms
29,696 KB
testcase_18 AC 51 ms
29,440 KB
testcase_19 AC 51 ms
29,568 KB
testcase_20 AC 50 ms
29,440 KB
testcase_21 AC 49 ms
29,568 KB
testcase_22 AC 49 ms
29,568 KB
testcase_23 AC 49 ms
29,440 KB
testcase_24 AC 50 ms
29,440 KB
testcase_25 AC 48 ms
29,312 KB
testcase_26 AC 55 ms
33,792 KB
testcase_27 AC 57 ms
33,792 KB
testcase_28 AC 49 ms
29,440 KB
testcase_29 AC 49 ms
29,400 KB
testcase_30 AC 48 ms
29,308 KB
testcase_31 AC 113 ms
54,400 KB
testcase_32 AC 91 ms
53,376 KB
testcase_33 AC 86 ms
49,920 KB
testcase_34 AC 105 ms
54,144 KB
testcase_35 AC 117 ms
54,400 KB
testcase_36 AC 109 ms
54,016 KB
testcase_37 AC 113 ms
54,272 KB
testcase_38 AC 93 ms
53,632 KB
testcase_39 AC 119 ms
54,528 KB
testcase_40 AC 73 ms
40,704 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 AC 45 ms
28,288 KB
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 AC 44 ms
28,288 KB
testcase_52 AC 45 ms
28,544 KB
testcase_53 AC 48 ms
28,544 KB
testcase_54 AC 48 ms
28,288 KB
testcase_55 AC 50 ms
28,544 KB
testcase_56 WA -
testcase_57 AC 48 ms
28,120 KB
testcase_58 AC 47 ms
28,032 KB
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 AC 148 ms
52,352 KB
testcase_63 AC 48 ms
28,288 KB
testcase_64 AC 45 ms
28,416 KB
testcase_65 AC 45 ms
28,032 KB
testcase_66 AC 47 ms
28,544 KB
testcase_67 AC 45 ms
187,184 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (189 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  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 System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using Compro.IO;
using static Compro.Common.ComproUtils;

namespace Compro
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var solver = new AtCoder.Solver();
            solver.Solve();
        }
    }
}


namespace AtCoder
{
    public class Solver
    {
        private readonly StreamScanner scanner;
        

        public Solver()
        {
            scanner = new StreamScanner(Console.OpenStandardInput());
        }

        public void Solve()
        {
            var n = scanner.NextInt();
            var a = scanner.ScanIntArray(n);
            Console.WriteLine(check(n, a) ? "Yes": "No");
        }

        private bool check(int n, int[] A)
        {
            if (n > 5555 || A.Contains(0))
                return true;

            var xor = A.Aggregate(0, (cur, nxt) => cur ^ nxt);
            if (xor != 0)
                return false;
            

            int m = (1 << 13);
            var dp = Enumerable.Repeat(INF, m).ToArray();
            dp[A[0]] = 1;
            foreach (var a in A[1..])
            {
                var ndp = Enumerable.Repeat(INF, m).ToArray();
                for (int i = 0; i < m; ++i)
                {
                    ndp[i] = Math.Min(ndp[i], dp[i]);
                    ndp[i ^ a] = Math.Min(ndp[i ^ a], dp[i] + 1);
                }
                dp = ndp;
            }
            return dp[0] != n;
        }
    }
}



namespace Compro.Common
{
    public static class ComproUtils
    {
        public static readonly long LINF = long.MaxValue / 2;
        public static readonly int INF = int.MaxValue / 2;

        public static readonly int[] dr = new[] { 0, 1, 0, -1 };
        public static readonly int[] dc = new[] { 1, 0, -1, 0 };
        public const string ds = "RBLF";

        public static long gcd(long x, long y) => y == 0 ? x : gcd(y, x % y);
        public static long lcm(long x, long y) => x * (y / gcd(x, y));


        /// <summary>
        /// nの約数を列挙する
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<long> GenDivisor(long n)
        {
            for (long i = 1L; i * i <= n; ++i)
            {
                if (n % i == 0)
                {
                    yield return i;
                    if (i * i != n) yield return n / i;
                } 
            }
        }


        /// <summary>
        /// aを素因数分解する Dict<long primeNumber, int count>
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        public static Dictionary<long, int> PrimeFactorization(long a)
        {
            var dict = new Dictionary<long, int>();

            if (a == 0)
                return dict;

            int cnt = 0;
            while (a % 2 == 0)
            {
                a /= 2;
                cnt++;
            }
            if (cnt > 0)
            {
                dict.Add(2, cnt);
            }


            for(long p = 3; p * p <= a; p += 2)
            {
                cnt = 0; 
                while (a % p == 0)
                {
                    cnt++;
                    a /= p;
                }
                dict.Add(p, cnt);
            }

            if (a > 1)
            {
                dict.Add(a, 1);
            }

            return dict;
        }
    }
}




namespace Compro.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;
    using System;

    public class StreamScanner
    {
        private readonly Stream stream;
        private readonly byte[] buffer = new byte[1024];
        private int size, ptr;
        private bool isEOF = false;

        public StreamScanner(Stream stream)
        {
            this.stream = stream;
            ptr = 0;
            size = 0;
        }

        private byte read()
        {
            if (isEOF) return 0;
            if (ptr >= size)
            {
                ptr = 0;
                size = stream.Read(buffer, 0, 1024);
                if (size <= 0)
                {
                    isEOF = true;
                    return 0;
                }
            }
            return buffer[ptr++];
        }

        public char Char()
        {
            byte b = 0;
            do { b = read(); } while ((b < 33 || 126 < b) && !isEOF);
            return (char)b;
        }

        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }

        public int NextInt() { return isEOF ? Int32.MinValue : Int32.Parse(Scan(), CultureInfo.InvariantCulture); }
        public long NextLong() { return isEOF ? Int64.MinValue : Int64.Parse(Scan(), CultureInfo.InvariantCulture); }
        public double NextDouble() { return isEOF ? Double.MinValue : Double.Parse(Scan(), CultureInfo.InvariantCulture); }

        public int[] ScanIntArray(int size)
        {
            var res = new int[size];
            for (int i = 0; i < size; ++i) 
                res[i] = NextInt();
            return res;
        }

        public long[] ScanLongArray(int size)
        {
            var res = new long[size];
            for (int i = 0; i < size; ++i)
                res[i] = NextLong();
            return res;
        }

        public double[] ScanDoubleArray(int size)
        {
            var res = new double[size];
            for (int i = 0; i < size; ++i)
                res[i] = NextDouble();
            return res;
        }
    }
}
0