Cod sursa(job #2576395)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 6 martie 2020 19:03:14
Problema Elementul majoritar Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 1000005;
int v[NMAX];
int n;

pair<int,int> elmaj(int v[], int n)
{
	int k = 0, cand = v[1];
	for (int i = 2; i <= n; i++)
	{
		if (cand == v[i])
			k++;
		else
			k--;
		if (k == 0)
		{
			k = 1;
			cand = v[i];
		}
	}
	int cnt = 0;
	pair<int, int>sol;
	for (int i = 1; i <= n; i++)
		if (cand == v[i])
			cnt++;
	if (cnt >= ((n / 2) + 1))
		return make_pair(cand,cnt);
	return make_pair(-1,-1);
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> v[i];
	pair<int, int> info = elmaj(v, n);
	if (info.first == -1)
		fout << "-1\n";
	else
		fout << info.first << " " << info.second << "\n";
	return 0;
}