#970409 (C#) No.2672 Subset Xor Sum

提出ソース

結果

問題	No.2672 Subset Xor Sum
ユーザー	tktk_snsn
提出日時	2024-04-06 23:49:13
言語	C# (.NET 8.0.203)
結果	WA
実行時間	-
コード長	5,864 bytes
コンパイル時間	9,360 ms
コンパイル使用メモリ	167,556 KB
実行使用メモリ	186,684 KB
最終ジャッジ日時	2024-10-01 04:09:05
合計ジャッジ時間	15,161 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	49 ms 28,416 KB
testcase_01	WA	-
testcase_02	AC	54 ms 30,720 KB
testcase_03	AC	48 ms 28,928 KB
testcase_04	AC	47 ms 28,544 KB
testcase_05	AC	57 ms 28,800 KB
testcase_06	AC	52 ms 28,928 KB
testcase_07	AC	54 ms 29,568 KB
testcase_08	AC	54 ms 29,696 KB
testcase_09	AC	54 ms 29,824 KB
testcase_10	AC	53 ms 28,672 KB
testcase_11	AC	53 ms 28,800 KB
testcase_12	AC	51 ms 30,080 KB
testcase_13	AC	51 ms 29,952 KB
testcase_14	AC	51 ms 29,824 KB
testcase_15	AC	50 ms 29,568 KB
testcase_16	AC	51 ms 30,080 KB
testcase_17	AC	50 ms 29,952 KB
testcase_18	AC	51 ms 29,824 KB
testcase_19	AC	50 ms 30,080 KB
testcase_20	AC	50 ms 29,824 KB
testcase_21	AC	51 ms 30,080 KB
testcase_22	AC	48 ms 28,404 KB
testcase_23	AC	48 ms 28,288 KB
testcase_24	AC	47 ms 28,672 KB
testcase_25	AC	49 ms 28,800 KB
testcase_26	AC	49 ms 28,800 KB
testcase_27	AC	48 ms 28,660 KB
testcase_28	AC	47 ms 28,544 KB
testcase_29	AC	48 ms 28,544 KB
testcase_30	AC	50 ms 29,824 KB
testcase_31	AC	118 ms 54,912 KB
testcase_32	AC	95 ms 54,016 KB
testcase_33	AC	88 ms 50,176 KB
testcase_34	AC	109 ms 54,144 KB
testcase_35	AC	121 ms 54,912 KB
testcase_36	AC	111 ms 54,528 KB
testcase_37	AC	130 ms 54,912 KB
testcase_38	AC	97 ms 54,016 KB
testcase_39	AC	125 ms 55,296 KB
testcase_40	AC	76 ms 40,960 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	AC	49 ms 28,800 KB
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	48 ms 28,544 KB
testcase_52	AC	50 ms 28,544 KB
testcase_53	AC	50 ms 28,544 KB
testcase_54	AC	50 ms 28,416 KB
testcase_55	AC	48 ms 28,532 KB
testcase_56	WA	-
testcase_57	AC	46 ms 28,800 KB
testcase_58	AC	46 ms 28,032 KB
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	AC	50 ms 29,312 KB
testcase_63	AC	45 ms 28,032 KB
testcase_64	AC	48 ms 29,056 KB
testcase_65	AC	45 ms 28,416 KB
testcase_66	WA	-
testcase_67	AC	45 ms 186,684 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (102 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/

ソースコード

raw source code

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 (A.Contains(0))
                return true;

            int bit = 0;
            foreach (var a in A)
                bit ^= a;

            if (bit != 0)
                return false;

            for (int ng = 0; ng < Math.Min(n, 5); ++ng)
            {
                var hash = new HashSet<int> { A[ng], };
                for (int i = 0; i < n - 1; ++i)
                {
                    if (i == ng) continue;
                    if (hash.Contains(A[i]))
                        return true;

                    var nxt = hash.Select(x => x ^ A[i]).ToArray();
                    foreach (var b in nxt)
                    {
                        hash.Add(b);
                    }
                }
            }
            return false;
        }
    }
}



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;
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード