Pagini recente » Cod sursa (job #803834) | Cod sursa (job #784349) | Cod sursa (job #926442) | Cod sursa (job #1757177) | Cod sursa (job #1308394)
#include <bits/stdc++.h>
using namespace std;
struct Trie
{
struct TrieNode
{
TrieNode *sons[2];
int cnt;
int dim;
TrieNode()
{
cnt = 0;
dim = 0;
sons[0] = sons[1] = NULL;
}
};
Trie()
{
R = new TrieNode();
}
TrieNode *R;
void insert( TrieNode *&root, int b, int nr )
{
if ( b == -1 )
{
root->cnt++;
root->dim = root->cnt;
}
else
{
int p = (bool)( nr & ( 1 << b ) );
if ( root->sons[p] == NULL )
root->sons[p] = new TrieNode();
insert( root->sons[p], b - 1, nr );
root->dim = 0;
if ( root->sons[0] != NULL )
root->dim += root->sons[0]->dim;
if ( root->sons[1] != NULL )
root->dim += root->sons[1]->dim;
}
}
void kth_order( TrieNode *&root, int b, int k, int &sol )
{
if ( b != -1 )
{
if ( root->sons[0] == NULL || root->sons[1] == NULL )
{
if ( root->sons[0] != NULL )
{
kth_order( root->sons[0], b - 1, k, sol );
}
if ( root->sons[1] != NULL )
{
sol |= ( 1 << b );
kth_order( root->sons[1], b - 1, k, sol );
}
if ( root->sons[0] == NULL && root->sons[1] == NULL )
cerr << "ERROR";
}
else
{
if ( k <= root->sons[0]->dim )
kth_order( root->sons[0], b - 1, k, sol );
else
{
sol |= ( 1 << b );
kth_order( root->sons[1], b - 1, k - root->sons[0]->dim, sol );
}
}
}
}
void insert( int number )
{
insert( R, 31, number );
}
int kth_order( int k )
{
int sol = 0;
kth_order( R, 31, k, sol );
return sol;
}
};
int N, K, a;
int main()
{
ifstream in("sdo.in");
ofstream out("sdo.out");
ios_base::sync_with_stdio( false );
in >> N >> K;
Trie T;
for ( int i = 1; i <= N; ++i )
{
in >> a;
T.insert( a );
}
out << T.kth_order( K );
return 0;
}