Cod sursa(job #1851494)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 19 ianuarie 2017 19:58:07
Problema Elementul majoritar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

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

int a[1000001];

int main()
{   int n, i, maj, vot = 1, ct = 0;
    fin >> n;
    for ( i = 1; i <= n; i++ )
         fin >> a[i];
    fin.close();
    maj = a[1];
    for ( i = 2; i <= n; i++ )
         if ( a[i] == maj ) vot++;
         else if ( vot > 0 ) vot--;
              else { maj = a[i];
                     vot = 1;
                   }
    for ( i = 1; i <= n; i++ )
         if ( a[i] == maj ) ct++;
    if ( ct >= n / 2 + 1 )
        fout << maj << " " << ct;
    else fout << -1;
    fout.close();
    return 0;
}