Cod sursa(job #2183904)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 23 martie 2018 16:05:40
Problema Elementul majoritar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int ap[110017][2];
const int M=110017;

int h(int x)
{
    return x%M;
}

int main()
{
    ifstream fin("elmaj.in");
    ofstream fout("elmaj.out");
    vector < int > v[110017];
    int p, n, i, j, ind, max, x;
    fin >> n;
    for (i=0; i<n; i++)
    {
        fin >> x;
        p=0;
        ind=h(x);
        for (j=0; j<v[ind].size(); j++)
            if (x==v[ind][j])
                p=1;
        if (ap[ind][0]==0)
        {
            ap[ind][0]=1;
            ap[ind][1]=x;
        }
        else if (ap[ind][1]==x)
            ap[ind][0]++;
    }
    p=0;
    for (i=0; i<110017; i++)
    {
        if (p)
            break;
        if (ap[i][0]>n/2)
        {
            p=1;
            max=ap[i][1];
        }
    }
    if (p)
        fout << "DA " << max;
    else
        fout << "NU";
    return 0;
}