Cod sursa(job #1641458)
Utilizator | Palade Thomas-Emanuel justsomedude | Data | 8 martie 2016 23:19:55 |
---|---|---|---|
Problema | Elementul majoritar | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin ("elmaj.in");
ofstream fout ("elmaj.out");
int a[1000009], N;
int main ()
{
int i, j, k;
int x, cnt;
fin >> N;
for (i=1; i<=N; i++)
fin >> a[i];
x = a[1]; cnt = 1;
for (j=2; j<=N; j++)
{
if (a[j] != x) cnt--;
else cnt++;
if (cnt < 0) x = a[j];
}
k = 0;
for (j=1; j<=N; j++)
if (a[j] == x)
k++;
if (k>=N/2+1)
fout << x << " " << k << "\n";
else
fout << "-1\n";
fin.close();
fout.close();
return 0;
}