Cod sursa(job #2421370)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 mai 2019 21:12:57
Problema Elementul majoritar Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <unistd.h>

#define CHUNK (1 << 24)
#define NMAX 1000000

static char buf[CHUNK];
static size_t bpos, v[NMAX];

static inline size_t read_int(void)
{
    size_t x = 0;

    while ('0' <= buf[bpos]) {
        x = x * 10 + (buf[bpos] - '0');
        bpos++;
    }

    bpos++;
    return x;
}

int main(void)
{
    size_t n, i, m = 0, k;

    freopen("elmaj.in", "r", stdin);
    freopen("elmaj.out", "w", stdout);

    read(STDIN_FILENO, buf, CHUNK);

    n = read_int();

    k = 0;

    for (i = 0; i < n; i++) {
        v[i] = read_int();
        if (k == 0) {
            m = v[i];
            k = 1;
        } else if (v[i] != m) {
            k--;
        } else if (v[i] == m) {
            k++;
        }
    }

    for (k = 0, i = 0; i < n; i++) {
        k += v[i] == m;
    }

    if (k > n / 2) {
        printf("%lu %lu", m, k);
    } else {
        puts("-1");
    }

    return 0;
}