Pagini recente » Cod sursa (job #852314) | Cod sursa (job #1720518) | Cod sursa (job #2106580) | Clasament testf | Cod sursa (job #1998163)
#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;
}
}
}