106 lines
2.4 KiB
Java
106 lines
2.4 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Comparator;
|
|
import java.util.List;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class F extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
int k = in.nextInt();
|
|
int m = in.nextInt();
|
|
int a = in.nextInt();
|
|
|
|
int votesLeft = m - a;
|
|
|
|
List<int[]> votes = new ArrayList<>();
|
|
for (int i = 0; i < n; i++) {
|
|
votes.add(new int[]{i, 0, 0});
|
|
}
|
|
|
|
for (int i = 0; i < a; i++) {
|
|
int vote = in.nextInt() - 1;
|
|
votes.get(vote)[1] += 1;
|
|
votes.get(vote)[2] += i;
|
|
}
|
|
|
|
votes.sort(new Comparator<int[]>() {
|
|
@Override
|
|
public int compare(int[] o1, int[] o2) {
|
|
int t = -Integer.compare(o1[1], o2[1]);
|
|
if (t != 0) {
|
|
return t;
|
|
}
|
|
return Integer.compare(o1[2], o2[2]);
|
|
}
|
|
});
|
|
int[] places = new int[n];
|
|
for (int i = 0; i < n; i++) {
|
|
places[votes.get(i)[0]] = i;
|
|
}
|
|
|
|
int[] answer = new int[n];
|
|
for (int candidate = 0; candidate < n; candidate++) {
|
|
int place = places[candidate];
|
|
|
|
int highestPossible = place;
|
|
int highestVotes = votes.get(place)[1];
|
|
|
|
{
|
|
int totalVotes = votes.get(place)[1] + votesLeft;
|
|
highestVotes = totalVotes;
|
|
|
|
for (int j = place - 1; j >= 0; j--) {
|
|
if (totalVotes > votes.get(j)[1]) {
|
|
highestPossible = j;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
int lowestPossible = place;
|
|
|
|
{
|
|
int avail = votesLeft;
|
|
int need = votes.get(place)[1] + 1;
|
|
for (int j = place + 1; j < n; j++) {
|
|
int cost = need - votes.get(j)[1];
|
|
if (cost <= avail) {
|
|
avail -= cost;
|
|
lowestPossible = j;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
boolean canWin = highestVotes > 0 && highestPossible < k;
|
|
boolean canLose = votes.get(place)[1] == 0 || lowestPossible >= k;
|
|
|
|
if (canWin && !canLose) {
|
|
answer[candidate] = 1;
|
|
} else if (!canWin && canLose) {
|
|
answer[candidate] = 3;
|
|
} else {
|
|
answer[candidate] = 2;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
out.print(answer[i] + " ");
|
|
}
|
|
}
|
|
}
|