Solutii la concursul acm 2013 etapa nationala partea I

Petru Trimbitas
17 iunie 2013

Duminică, 16 iunie a avut loc faza naţionala a concursului acm icpc. Pagina concursului o gasiţi aici
iar clasamentul aici
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.

Voi prezenta in continuare o parte din probleme şi soluţiile acestora

G. Election Time

Aceasta a fost cea mai simplă problemă din concurs, fiind rezolvată de marea majoritate a echipelor.
Problema ne cerea să determinăm câştigătorul alegerilor dupa 2 tururi ştiind cate voturi va obţine fiecare candidat in cele 2 tururi. În plus după primul tur rămâneau doar primii k candidati.

O soluţie ar fi sortarea candidaţilor descresrescător după numărul de voturi primite în primul tur, iar pe urmă sortarea primilor k după numărul de votur din al doilea tur.

#include <iostream>
#include <algorithm>
#define DN 50005
using namespace std;

int n,k,ind[DN],a[DN],b[DN];

bool cmp(int x,int y) {
	return a[x]>a[y];
}

bool cmp2(int x,int y) {
	return b[x]>b[y];
}

int main() {
	cin>>n>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i]>>b[i];
		ind[i]=i;
	}
	sort(ind+1,ind+n+1,cmp);
	sort(ind+1,ind+k+1,cmp2);
	cout<<ind[1]<<'\n';
}