結果
| 問題 | No.5004 Room Assignment |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2021-12-05 19:29:49 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 966 ms / 5,000 ms |
| コード長 | 7,544 bytes |
| コンパイル時間 | 4,459 ms |
| 実行使用メモリ | 238,532 KB |
| スコア | 138,988,706 |
| 平均クエリ数 | 7637.91 |
| 最終ジャッジ日時 | 2021-12-05 19:31:36 |
| 合計ジャッジ時間 | 101,694 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;
public class Main {
private static final int VAL = -1000000;
private int T;
private int R;
private int p = 0;
private int[] tim = new int[5555];
private int[][] tim2 = new int[5555][5555];
private int[] S = new int[5555];
private ArrayList<ArrayList<Integer>> groups = new ArrayList<>();
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (Scanner in = new Scanner(System.in)) {
T = in.nextInt();
R = in.nextInt();
for (int i = 0; i < tim2.length; i++) {
Arrays.fill(tim2[i], VAL);
}
for (int t = 0; t < T; t++) {
int N = in.nextInt();
int[] s = IntStream.range(0, N).map(i -> in.nextInt()).toArray();
ArrayList<A> list = solve(N, s, t);
StringBuilder sb = new StringBuilder();
sb.append(list.size() + "\n");
for (A a : list) {
sb.append(a.i + " " + a.j + "\n");
}
System.out.print(sb.toString());
System.out.flush();
}
}
}
private ArrayList<A> solve(int N, int[] s, int t) {
ArrayList<A> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
p++;
tim[p] = t;
S[p] = s[i];
ArrayList<Integer> best = null;
int bestV = 0;
for (int j = 0; j < groups.size(); j++) {
ArrayList<Integer> g = groups.get(j);
for (int k = 0; k < g.size(); k++) {
tim2[p][g.get(k)] = t;
tim2[g.get(k)][p] = t;
}
g.add(p);
int evaluation = evaluate(g);
if (evaluation > bestV) {
bestV = evaluation;
best = g;
}
g.remove(g.size() - 1);
for (int k = 0; k < g.size(); k++) {
tim2[p][g.get(k)] = VAL;
tim2[g.get(k)][p] = VAL;
}
}
if (best == null) {
ArrayList<Integer> group = new ArrayList<>();
group.add(p);
groups.add(group);
} else {
for (int k = 0; k < best.size(); k++) {
tim2[p][best.get(k)] = t;
tim2[best.get(k)][p] = t;
}
best.add(p);
list.add(new A(p, best.get(0)));
if (best.size() == R) {
ArrayList<Integer> listS = new ArrayList<>();
for (int j = 0; j < best.size(); j++) {
listS.add(S[best.get(j)]);
}
ArrayList<Integer> listTime = new ArrayList<>();
for (int j = 0; j < best.size(); j++) {
listTime.add(tim[best.get(j)]);
}
groups.remove(best);
}
}
}
if (t == T - 1) {
for (int i = 0; i < groups.size(); i++) {
ArrayList<Integer> gi = groups.get(i);
for (int j = i + 1; j < groups.size(); j++) {
ArrayList<Integer> gj = groups.get(j);
if (gi.size() + gj.size() > R) {
continue;
}
int ei = evaluate(gi);
int ej = evaluate(gj);
for (int k = 0; k < gi.size(); k++) {
for (int k2 = 0; k2 < gj.size(); k2++) {
tim2[gj.get(k2)][gi.get(k)] = t;
tim2[gi.get(k)][gj.get(k2)] = t;
}
}
gi.addAll(gj);
if (evaluate(gi) > ei + ej) {
groups.remove(gj);
if (gi.size() == R) {
groups.remove(gi);
i--;
}
for (int k2 = 0; k2 < gj.size(); k2++) {
list.add(new A(gi.get(0), gj.get(k2)));
}
break;
} else {
for (Integer p : gj) {
boolean b = gi.remove(p);
}
for (int k = 0; k < gi.size(); k++) {
for (int k2 = 0; k2 < gj.size(); k2++) {
tim2[gj.get(k2)][gi.get(k)] = VAL;
tim2[gi.get(k)][gj.get(k2)] = VAL;
}
}
}
}
}
}
return list;
}
private int evaluate(ArrayList<Integer> g) {
int E = 0;
for (int i = 0; i < g.size(); i++) {
int pi = g.get(i).intValue();
for (int j = i + 1; j < g.size(); j++) {
int pj = g.get(j).intValue();
E += Math.abs(tim[pi] - tim2[pi][pj]);
E += Math.abs(tim[pj] - tim2[pi][pj]);
}
}
int maxS = (int) -1e9;
int minS = (int) 1e9;
for (int i = 0; i < g.size(); i++) {
int p = g.get(i).intValue();
maxS = Math.max(maxS, S[p]);
minS = Math.min(minS, S[p]);
}
int mean = (minS + maxS) / 2;
int abs = Math.abs(mean - 50);
if (abs < 5) {
if (maxS - minS > 2) {
return 0;
}
} else if (abs < 10) {
if (maxS - minS > 2) {
return 0;
}
} else if (abs < 15) {
if (maxS - minS > 3) {
return 0;
}
} else if (abs < 20) {
if (maxS - minS > 3) {
return 0;
}
} else if (abs < 25) {
if (maxS - minS > 3) {
return 0;
}
} else if (abs < 30) {
if (maxS - minS > 4) {
return 0;
}
} else if (abs < 35) {
if (maxS - minS > 5) {
return 0;
}
} else {
if (maxS - minS > 5) {
return 0;
}
}
int ce = g.size() == 1 ? 0 : g.size() == 2 ? 1 : g.size() == 3 ? 3 : g.size() == 4 ? 6 : -1000;
return Math.max(0, ce * (200 - (maxS - minS) * (maxS - minS)) - E);
}
}
class A {
int i;
int j;
public A(int i, int j) {
this.i = i;
this.j = j;
}
}
class UnionFind {
int[] data;
UnionFind(int size) {
data = new int[size];
Arrays.fill(data, -1);
}
boolean unionSet(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (data[y] < data[x]) {
int swap = x;
x = y;
y = swap;
}
data[x] += data[y];
data[y] = x;
}
return x != y;
}
boolean findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : (data[x] = root(data[x]));
}
int size(int x) {
return -data[root(x)];
}
}