Cod sursa(job #1077733)

Utilizator IoannaPandele Ioana Ioanna Data 11 ianuarie 2014 16:55:37
Problema Elementul majoritar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#define NMAX 1000001

using namespace std;

int n;
int v[NMAX];

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

void read() {
    in>>n;
    for (int i = 0; i < n; i++) {
        in>>v[i];
    }
}

int part(int st, int dr) {
    int i = st - 1;
    int j = dr + 1;
    int p = v[(st + dr) / 2];
    int aux;
    while(1) {
        do {i++;} while (v[i] < p);
        do {j--;} while (v[j] > p);
        if (i < j) {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
        } else return j;
    }
}
void quicks(int st, int dr) {
    if (st < dr) {
        int p = part(st, dr);
        quicks(st, p);
        quicks(p + 1, dr);
    }
}

void solve() {
    v[n] = v[n - 1] + 1;
    int cnt = 1;
    int nr = v[0];
    for (int i = 0; i < n; i++) {
        if (v[i] == v[i + 1]) {
            cnt++;
        } else {
            if (cnt >= (n / 2 + 1)) {
                out<<nr<<" "<<cnt;
                return;
            } else {
                cnt = 1;
                nr = v[i + 1];
            }
        }
    }
    out<<"-1";
}

int main() {
    read();
    quicks(0, n - 1);
    solve();
    return 0;
}