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

提出ソース

結果

問題	No.2672 Subset Xor Sum
ユーザー	tktk_snsn
提出日時	2024-04-06 23:39:02
言語	C# (.NET 8.0.203)
結果	WA
実行時間	-
コード長	5,718 bytes
コンパイル時間	7,934 ms
コンパイル使用メモリ	158,260 KB
実行使用メモリ	177,852 KB
最終ジャッジ日時	2024-04-06 23:39:23
合計ジャッジ時間	18,450 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	82 ms 30,756 KB
testcase_01	AC	85 ms 30,628 KB
testcase_02	AC	78 ms 30,884 KB
testcase_03	AC	81 ms 30,756 KB
testcase_04	AC	79 ms 30,756 KB
testcase_05	AC	80 ms 30,884 KB
testcase_06	AC	81 ms 30,884 KB
testcase_07	AC	79 ms 30,756 KB
testcase_08	AC	80 ms 30,756 KB
testcase_09	AC	79 ms 30,756 KB
testcase_10	AC	81 ms 30,884 KB
testcase_11	AC	81 ms 30,884 KB
testcase_12	AC	81 ms 30,756 KB
testcase_13	AC	81 ms 30,756 KB
testcase_14	AC	86 ms 30,756 KB
testcase_15	AC	80 ms 30,756 KB
testcase_16	AC	80 ms 30,756 KB
testcase_17	AC	91 ms 30,756 KB
testcase_18	AC	83 ms 30,756 KB
testcase_19	AC	81 ms 30,756 KB
testcase_20	AC	81 ms 30,756 KB
testcase_21	AC	80 ms 30,756 KB
testcase_22	AC	81 ms 30,756 KB
testcase_23	AC	80 ms 30,756 KB
testcase_24	AC	81 ms 30,756 KB
testcase_25	AC	81 ms 30,756 KB
testcase_26	AC	84 ms 31,140 KB
testcase_27	AC	81 ms 31,140 KB
testcase_28	AC	79 ms 31,012 KB
testcase_29	AC	81 ms 31,012 KB
testcase_30	AC	79 ms 30,756 KB
testcase_31	AC	152 ms 55,972 KB
testcase_32	AC	113 ms 54,948 KB
testcase_33	AC	105 ms 51,236 KB
testcase_34	AC	133 ms 55,460 KB
testcase_35	AC	149 ms 55,972 KB
testcase_36	AC	151 ms 55,588 KB
testcase_37	AC	146 ms 55,844 KB
testcase_38	AC	117 ms 54,948 KB
testcase_39	AC	155 ms 56,100 KB
testcase_40	AC	92 ms 41,892 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	AC	72 ms 31,012 KB
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	74 ms 31,012 KB
testcase_52	AC	74 ms 31,012 KB
testcase_53	AC	72 ms 31,012 KB
testcase_54	AC	74 ms 31,012 KB
testcase_55	AC	74 ms 31,012 KB
testcase_56	WA	-
testcase_57	AC	78 ms 30,756 KB
testcase_58	AC	72 ms 30,500 KB
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	AC	81 ms 31,396 KB
testcase_63	AC	71 ms 30,756 KB
testcase_64	AC	73 ms 30,884 KB
testcase_65	AC	71 ms 30,500 KB
testcase_66	AC	73 ms 30,500 KB
testcase_67	AC	70 ms 177,852 KB

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

コンパイルメッセージ

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

ソースコード

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;

            var hash = new HashSet<int>();
            hash.Add(A[0]);
            foreach (var a in A[1..^1])
            {
                if (hash.Contains(a))
                    return true;
                
                var nxt = hash.Select(x => x ^ a).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

結果

テストケース

コンパイルメッセージ

ソースコード