Cod sursa(job #1380103)
Utilizator | Data | 6 martie 2015 21:59:53 | |
---|---|---|---|
Problema | Elementul majoritar | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
ifstream fin("elmaj.in");
ofstream fout("elmaj.out");
int n, a[MAXN], cnt, maj;
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> a[i];
for (int i = 1; i <= n; ++i)
{
if (cnt == 0)
{
maj = a[i];
cnt++;
}
else if (a[i] == maj)
cnt++;
else
cnt--;
}
cnt = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] == maj)
cnt++;
}
if (cnt >= n / 2 + 1)
fout << maj << " " << cnt;
else
fout << -1;
return 0;
}