Cod sursa(job #1312061)

Utilizator thesvcoolmanLucian Bicsi thesvcoolman Data 8 ianuarie 2015 21:01:32
Problema Elementul majoritar Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream fin("elmaj.in");
ofstream fout("elmaj.out");

vector<int> CAND, AP;

void adaugaCand(int i) {
    int in;
    for(in=0; in<CAND.size(); in++) {
        if(CAND[in] == i) {
            break;
        }
    }
    if(in == CAND.size()) {
        CAND.push_back(i);
        AP.push_back(0);
    }
}

bool bsearch(int val, int &poz, int b, int e) {

    if(b == e) {
        poz = b;
        return val == CAND[b];
    }
    if(val>CAND[(b+e)/2])
        return bsearch(val, poz, (b+e)/2+1, e);
    else return bsearch(val, poz, b, (b+e)/2);
}

void afis(vector<int> &v) {
    for(int i=0; i<v.size(); i++) {
        fout<<v[i]<<" ";
    }fout<<endl;
}

int n, last, cur;
int main() {
    fin>>n>>last;
    for(int i=2; i<=n; i++) {
        fin>>cur;
        if(cur == last) {
            if(CAND.size() <= 16)
                adaugaCand(cur);
        }
        last = cur;
    }

    sort(CAND.begin(), CAND.end());
    fin.close();
    ifstream fin("elmaj.in");
    fin>>n;

    int poz;
    for(int i=1; i<=n; i++) {
        fin>>cur;
        if(bsearch(cur, poz, 0, CAND.size()-1))
            AP[poz]++;
    }

    //afis(CAND);
    //afis(AP);

    for(int i=0; i<CAND.size(); i++) {
        if(AP[i] > n/2) {
            fout<<CAND[i]<<" "<<AP[i];
            return 0;
        }
    }
    fout<<-1;

    return 0;
}