結果

問題 No.2977 Kth Xor Pair
ユーザー kakel-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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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