Cod sursa(job #1998163)

Utilizator MaligMamaliga cu smantana Malig Data 6 iulie 2017 19:42:32
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;
ifstream in("elmajk.in");
ofstream out("elmajk.out");

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 1e6 + 5;

int N,K,nrSol;
int v[NMax],sol[NMax];
bool vis[NMax];

void solve(int,int,int);
int part(int,int);

int main() {
    in>>N>>K;

    int nr=0,cand=0;
    for (int i=1;i <= N;++i) {
        in>>v[i];
    }

    srand(time(0));
    int part = N/K;
    for (int i=1;i * part <= N;++i) {
        solve(1,N,i*part);

        int val = v[i*part];
        if (vis[val]) {
            continue;
        }
        vis[val] = true;

        int nr = 0;
        for (int j=1;j <= N;++j) {
            if (v[j] == val) {
                ++nr;
            }
        }

        if (nr > part) {
            sol[++nrSol] = val;
        }
    }

    sort(sol+1,sol+nrSol+1);

    bool ok = false;
    for (int i=1;i <= nrSol;++i) {
        out<<sol[i]<<' ';
        ok = true;
    }

    if (!ok) {
        out<<"-1\n";
    }

    in.close();out.close();
    return 0;
}

void solve(int st,int dr,int K) {
    if (st >= dr) {
        return;
    }

    int idx = part(st,dr);

    if (K <= idx) {
        solve(st,idx,K);
    }
    else {
        solve(idx+1,dr,K);
    }
}
int part(int st,int dr) {
    int idx = rand() % (dr-st+1) + st;
    swap(v[st],v[idx]);

    int pivot = v[st], i = st-1, j = dr+1;
    while (true) {
        do {
            ++i;
        }
        while (v[i] < pivot);

        do {
            --j;
        }
        while (v[j] > pivot);

        if (i < j) {
            swap(v[i],v[j]);
        }
        else {
            return j;
        }
    }
}