結果

問題 No.2672 Subset Xor Sum
ユーザー tktk_snsntktk_snsn
提出日時 2024-04-07 00:22:07
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 5,843 bytes
コンパイル時間 6,900 ms
コンパイル使用メモリ 158,712 KB
実行使用メモリ 177,624 KB
最終ジャッジ日時 2024-04-07 00:22:26
合計ジャッジ時間 16,085 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
31,140 KB
testcase_01 AC 77 ms
31,140 KB
testcase_02 AC 78 ms
31,396 KB
testcase_03 AC 77 ms
31,396 KB
testcase_04 AC 76 ms
31,396 KB
testcase_05 AC 76 ms
31,396 KB
testcase_06 AC 77 ms
31,396 KB
testcase_07 AC 74 ms
31,396 KB
testcase_08 AC 77 ms
31,396 KB
testcase_09 AC 77 ms
31,396 KB
testcase_10 AC 77 ms
31,396 KB
testcase_11 AC 82 ms
31,396 KB
testcase_12 AC 75 ms
31,396 KB
testcase_13 AC 75 ms
31,396 KB
testcase_14 AC 76 ms
31,396 KB
testcase_15 AC 77 ms
31,396 KB
testcase_16 AC 77 ms
31,396 KB
testcase_17 AC 76 ms
31,396 KB
testcase_18 AC 77 ms
31,396 KB
testcase_19 AC 76 ms
31,396 KB
testcase_20 AC 79 ms
31,396 KB
testcase_21 AC 77 ms
31,396 KB
testcase_22 AC 79 ms
31,396 KB
testcase_23 AC 77 ms
31,396 KB
testcase_24 AC 77 ms
31,396 KB
testcase_25 AC 78 ms
31,396 KB
testcase_26 AC 86 ms
36,004 KB
testcase_27 AC 86 ms
36,004 KB
testcase_28 AC 76 ms
31,524 KB
testcase_29 AC 78 ms
31,524 KB
testcase_30 AC 78 ms
31,396 KB
testcase_31 AC 155 ms
55,716 KB
testcase_32 AC 114 ms
54,564 KB
testcase_33 AC 106 ms
50,852 KB
testcase_34 AC 156 ms
55,076 KB
testcase_35 AC 150 ms
55,588 KB
testcase_36 AC 141 ms
55,332 KB
testcase_37 AC 148 ms
55,588 KB
testcase_38 AC 117 ms
54,564 KB
testcase_39 AC 160 ms
55,844 KB
testcase_40 AC 88 ms
41,636 KB
testcase_41 AC 126 ms
54,820 KB
testcase_42 AC 171 ms
55,460 KB
testcase_43 AC 136 ms
55,204 KB
testcase_44 AC 159 ms
55,844 KB
testcase_45 AC 130 ms
55,076 KB
testcase_46 AC 70 ms
30,756 KB
testcase_47 AC 71 ms
30,756 KB
testcase_48 AC 69 ms
30,756 KB
testcase_49 AC 69 ms
30,756 KB
testcase_50 AC 71 ms
30,756 KB
testcase_51 AC 74 ms
30,756 KB
testcase_52 AC 73 ms
30,756 KB
testcase_53 AC 73 ms
30,756 KB
testcase_54 AC 75 ms
30,756 KB
testcase_55 AC 74 ms
30,756 KB
testcase_56 AC 72 ms
30,756 KB
testcase_57 AC 72 ms
30,500 KB
testcase_58 AC 74 ms
30,244 KB
testcase_59 AC 71 ms
30,116 KB
testcase_60 AC 69 ms
30,372 KB
testcase_61 AC 72 ms
30,244 KB
testcase_62 AC 173 ms
54,436 KB
testcase_63 AC 70 ms
30,500 KB
testcase_64 AC 70 ms
30,628 KB
testcase_65 AC 71 ms
30,244 KB
testcase_66 AC 74 ms
30,756 KB
testcase_67 AC 70 ms
177,624 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (124 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.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)
        {
            var xor = A.Aggregate(0, (cur, nxt) => cur ^ nxt);
            if (xor != 0)
            {
                return false;
            }

            if (n > 5555 || A.Contains(0))
            {
                return true;
            }

            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