Cod sursa(job #2591868)

Utilizator dancu_mihai13Dancu Mihai dancu_mihai13 Data 31 martie 2020 16:22:04
Problema Elementul majoritar Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

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

const int NMAX = 100000;

void citire(int v[NMAX], int &n)
{
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> v[i];
}

void boyermoore(int v[NMAX], int n)
{
    int ct = 1, curent = v[0];
    for(int i = 1; i < n; i++)
        if(v[i] == curent)
            ct++;
        else
            if(ct == 0)
            {
                ct = 1;
                curent = v[i];
            }
            else
                ct--;
    ct = 0;
    for(int i = 0; i < n; i++)
        if(v[i] == curent)
            ct++;
    if(ct > n / 2)
        fout << curent << ' ' << ct;
    else
        fout << -1;
}

int main()
{
    int n, v[NMAX]; citire(v, n);
    boyermoore(v, n);
    return 0;
}