Cod sursa(job #1538578)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 29 noiembrie 2015 14:05:42
Problema Elementul majoritar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <int> kmajority(vector <int> &v, int k) {
	vector <pair<int, int> >cnt(k - 1);
	for(auto it : v) {
		bool found = false;
		for(int i = 0 ; i < k - 1 ; ++ i)
			if(cnt[i].first == it) {
				++ cnt[i].second;
				found = true;
			}
		if(!found) {
			found = false;
			for(int i = 0 ; i < k - 1 ; ++ i) {
				if(cnt[i].first == 0) {
					cnt[i] = make_pair(it, 1);
					found = true;
				}
			}
			if(!found)
				for(int i = 0 ; i < k - 1 ; ++ i) {
					cnt[i].second --;
					if(cnt[i].second == 0)
						cnt[i] = make_pair(0, 0);
				}
		}
	}
	vector <int> res;
	for(int i = 0 ; i < k - 1 ; ++ i) {
		if(cnt[i].first && cnt[i].second) {
			int actcnt = 0;
			for(auto it : v)
				if(it == cnt[i].first)
					actcnt ++;
			if(actcnt > v.size() / k)
				res.push_back(cnt[i].first);
		}
	}
	return res;
}

int main() {
	ifstream fin("elmaj.in");
	ofstream fout("elmaj.out");
	int n, k = 2;
	fin >> n;
	vector <int> v;
	for(int i = 0 ; i < n ; ++ i) {
		int x;
		fin >> x;
		v.push_back(x);
	}
	for(auto el : kmajority(v, k))
		fout << el << ' ';
}