結果
問題 | No.5004 Room Assignment |
ユーザー |
![]() |
提出日時 | 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)];}}