Cod sursa(job #532548)

Utilizator GagosGagos Radu Vasile Gagos Data 11 februarie 2011 21:47:17
Problema Statistici de ordine Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

#define MOD 2000003

using namespace std;

typedef pair <int, long long> pr;
typedef pr * ppr;

int N, K;
int ind, sum, position, counter, remainder, modulo;
int L[340];
long long rv, answer;
vector <ppr> H[MOD + 4];
vector <ppr> :: iterator it;

int main()
{
    ifstream f("sdo.in");

    f >> N >> K;

    for(ind = 0; ind < N; ++ind)
    {
        f >> rv;

        ppr key = new pr();

        key->first = rv / MOD + 1;
        key->second = rv;

        modulo = rv % MOD;

        if(H[modulo].size() == 0)
        {
            ppr max = new pr();

            max->first = 0;
            max->second = 0;

            H[modulo].push_back(max);
        }
        if(key->first > H[modulo][0]->second)
            H[modulo][0]->second = key->first;

        H[modulo].push_back(key);
        ++L[key->first];
    }

    f.close();

    ind = 0;

    while(sum < K)
        sum += L[++ind];

    position = ind;
    sum -= L[position];
    remainder = K - sum;

    for(ind = 0, counter = 1; ind < MOD && counter <= remainder; ++ind)
    {
        if(H[ind].size() == 0)
            continue;
        if(H[ind].at(0)->second >= position)
        {
            for(it = H[ind].begin(); it != H[ind].end(); ++it)
                if((*it)->first == position)
                {
                    if(counter != remainder)
                        ++counter;
                    else
                    {
                        answer = (*it)->second;
                        ++counter;

                        break;
                    }
                }
        }
    }

    ofstream g("sdo.out");

    g << answer;

    g.close();

    cout << sizeof(H);

    return 0;
}