結果

問題 No.2977 Kth Xor Pair
ユーザー vjudge1
提出日時 2025-02-14 18:58:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,701 ms / 3,000 ms
コード長 1,406 bytes
コンパイル時間 1,775 ms
コンパイル使用メモリ 191,700 KB
実行使用メモリ 41,428 KB
最終ジャッジ日時 2025-02-14 19:00:27
合計ジャッジ時間 62,200 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:81:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |         scanf("%d%lld",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:82:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |         for(i=1;i<=n;i++) scanf("%d",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2e5+10;
struct Trie
{
	#define type ll
	static const int LOG=33;
	static const int K=LOG+2;
	int rt,root[MAX],tot,ch[MAX*K][2],cnt[MAX*K];
	Trie &operator[](const int _rt){this->rt=_rt;return *this;}
	int newnode()
	{
		tot++;
		memset(ch[tot],0,sizeof ch[tot]);
		cnt[tot]=0;
		return tot;
	}
	void init(int n=1)
	{
		ch[0][0]=ch[0][1]=cnt[0]=0;
		tot=1;
		for(int i=0;i<=n;i++) root[i]=0;
		rt=1;
	}
	void insert(type x)
	{
		int id,t,i;
		if(!root[rt]) root[rt]=newnode();
		id=root[rt];
		for(i=LOG;~i;i--)
		{
			cnt[id]++;
			t=(x>>i)&1;
			if(!ch[id][t]) ch[id][t]=newnode();
			id=ch[id][t];
		}
		cnt[id]++;
	}
	type count_y(type x,type limt) // count y: x xor y <= limt
	{
		int id,i;
		type res,t;
		if(!root[rt]) return 0;
		id=root[rt];
		res=0;
		for(i=LOG;~i;i--)
		{
			t=(x>>i)&1;
			if((limt>>i)&1)
			{
				res+=cnt[ch[id][t]];
				id=ch[id][t^1];
			}
			else id=ch[id][t];
		}
		res+=cnt[id];
		return res;
	}
	#undef type
}tr;
int a[MAX],n;
ll k;
int ck(ll x)
{
	int i;
	ll res;
	tr.init();
	res=0;
	for(i=1;i<=n;i++)
	{
		res+=tr.count_y(a[i],x);
		tr.insert(a[i]);
	}
	return res>=k;
}
int main()
{
	int i;
	ll l,r,mid;
	scanf("%d%lld",&n,&k);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	l=0;
	r=2e9;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(ck(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
	return 0;
}
0