Cod sursa(job #1308394)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 4 ianuarie 2015 00:25:52
Problema Statistici de ordine Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#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;
}