結果

問題 No.2977 Kth Xor Pair
ユーザー kakel-sankakel-san
提出日時 2024-12-24 21:56:24
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 871 ms / 3,000 ms
コード長 4,925 bytes
コンパイル時間 15,427 ms
コンパイル使用メモリ 165,584 KB
実行使用メモリ 235,508 KB
最終ジャッジ日時 2024-12-24 21:57:03
合計ジャッジ時間 36,815 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
30,592 KB
testcase_01 AC 53 ms
30,592 KB
testcase_02 AC 58 ms
31,488 KB
testcase_03 AC 58 ms
31,488 KB
testcase_04 AC 63 ms
31,488 KB
testcase_05 AC 57 ms
31,488 KB
testcase_06 AC 58 ms
31,488 KB
testcase_07 AC 409 ms
93,140 KB
testcase_08 AC 837 ms
134,116 KB
testcase_09 AC 666 ms
119,384 KB
testcase_10 AC 650 ms
119,564 KB
testcase_11 AC 722 ms
119,440 KB
testcase_12 AC 701 ms
119,800 KB
testcase_13 AC 745 ms
119,652 KB
testcase_14 AC 381 ms
87,040 KB
testcase_15 AC 629 ms
111,808 KB
testcase_16 AC 742 ms
122,920 KB
testcase_17 AC 727 ms
122,992 KB
testcase_18 AC 858 ms
122,920 KB
testcase_19 AC 871 ms
125,684 KB
testcase_20 AC 743 ms
122,788 KB
testcase_21 AC 733 ms
122,972 KB
testcase_22 AC 867 ms
112,128 KB
testcase_23 AC 744 ms
112,332 KB
testcase_24 AC 713 ms
112,460 KB
testcase_25 AC 756 ms
122,872 KB
testcase_26 AC 719 ms
112,200 KB
testcase_27 AC 312 ms
89,456 KB
testcase_28 AC 177 ms
80,196 KB
testcase_29 AC 197 ms
83,944 KB
testcase_30 AC 261 ms
82,708 KB
testcase_31 AC 245 ms
90,472 KB
testcase_32 AC 232 ms
75,920 KB
testcase_33 AC 208 ms
83,468 KB
testcase_34 AC 206 ms
82,260 KB
testcase_35 AC 202 ms
235,508 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (95 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 static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, k) = (c[0], c[1]);
        var a = NList;

        var initGroup = new Group();
        initGroup.Same = true;
        for (var i = 0; i < n; ++i) initGroup.Group1.Add(i);
        var glist = new List<Group>{ initGroup };
        var ans = 0;
        for (var i = 29; i >= 0; --i)
        {
            var nglist0 = new List<Group>();
            var nglist1 = new List<Group>();
            var zerocount = 0L;
            foreach (var g in glist)
            {
                if (g.Same)
                {
                    var ng00 = new Group();
                    ng00.Same = true;
                    var ng01 = new Group();
                    ng01.Same = true;
                    var ng1 = new Group();
                    foreach (var idx in g.Group1)
                    {
                        if (((a[idx] >> i) & 1) == 0)
                        {
                            ng00.Group1.Add(idx);
                            ng1.Group1.Add(idx);
                        }
                        else
                        {
                            ng01.Group1.Add(idx);
                            ng1.Group2.Add(idx);
                        }
                    }
                    if (ng00.Group1.Count > 1)
                    {
                        zerocount += (long)ng00.Group1.Count * (ng00.Group1.Count - 1) / 2;
                        nglist0.Add(ng00);
                    }
                    if (ng01.Group1.Count > 1)
                    {
                        zerocount += (long)ng01.Group1.Count * (ng01.Group1.Count - 1) / 2;
                        nglist0.Add(ng01);
                    }
                    if (ng1.Group1.Count > 0 && ng1.Group2.Count > 0)
                    {
                        nglist1.Add(ng1);
                    }
                }
                else
                {
                    var ng00 = new Group();
                    var ng01 = new Group();
                    var ng10 = new Group();
                    var ng11 = new Group();
                    foreach (var idx in g.Group1)
                    {
                        if (((a[idx] >> i) & 1) == 0)
                        {
                            ng00.Group1.Add(idx);
                            ng10.Group1.Add(idx);
                        }
                        else
                        {
                            ng01.Group1.Add(idx);
                            ng11.Group1.Add(idx);
                        }
                    }
                    foreach (var idx in g.Group2)
                    {
                        if (((a[idx] >> i) & 1) == 0)
                        {
                            ng00.Group2.Add(idx);
                            ng11.Group2.Add(idx);
                        }
                        else
                        {
                            ng01.Group2.Add(idx);
                            ng10.Group2.Add(idx);
                        }
                    }
                    if (ng00.Group1.Count > 0 && ng00.Group2.Count > 0)
                    {
                        zerocount += (long)ng00.Group1.Count * ng00.Group2.Count;
                        nglist0.Add(ng00);
                    }
                    if (ng01.Group1.Count > 0 && ng01.Group2.Count > 0)
                    {
                        zerocount += (long)ng01.Group1.Count * ng01.Group2.Count;
                        nglist0.Add(ng01);
                    }
                    if (ng10.Group1.Count > 0 && ng10.Group2.Count > 0)
                    {
                        nglist1.Add(ng10);
                    }
                    if (ng11.Group1.Count > 0 && ng11.Group2.Count > 0)
                    {
                        nglist1.Add(ng11);
                    }
                }
            }
            if (zerocount >= k)
            {
                glist = nglist0;
            }
            else
            {
                glist = nglist1;
                k -= zerocount;
                ans += 1 << i;
            }
        }
        WriteLine(ans);
    }
    class Group
    {
        public bool Same;
        public List<int> Group1 = new List<int>();
        public List<int> Group2 = new List<int>();
        public override string ToString()
        {
            return $"f: {Same}\ng1: {string.Join(" ", Group1)}\ng2: {string.Join(" ", Group2)}";
        }
    }
}
0