結果
| 問題 | No.382 シャイな人たち (2) |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-06-24 22:25:19 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 6,962 ms / 8,000 ms |
| コード長 | 11,058 bytes |
| コンパイル時間 | 2,656 ms |
| コンパイル使用メモリ | 84,024 KB |
| 実行使用メモリ | 61,220 KB |
| 最終ジャッジ日時 | 2024-10-11 21:17:16 |
| 合計ジャッジ時間 | 123,459 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 6,962 ms
60,008 KB |
| testcase_01 | AC | 6,508 ms
60,124 KB |
| testcase_02 | AC | 5,683 ms
59,872 KB |
| testcase_03 | AC | 6,755 ms
58,816 KB |
| testcase_04 | AC | 5,437 ms
59,744 KB |
| testcase_05 | AC | 5,918 ms
60,020 KB |
| testcase_06 | AC | 4,951 ms
61,196 KB |
| testcase_07 | AC | 5,937 ms
59,612 KB |
| testcase_08 | AC | 4,599 ms
61,220 KB |
| testcase_09 | AC | 6,709 ms
57,692 KB |
| testcase_10 | AC | 5,124 ms
60,112 KB |
| testcase_11 | AC | 5,843 ms
60,528 KB |
| testcase_12 | AC | 4,609 ms
59,492 KB |
| testcase_13 | AC | 6,043 ms
59,628 KB |
| testcase_14 | AC | 5,165 ms
57,412 KB |
| testcase_15 | AC | 5,710 ms
58,448 KB |
| testcase_16 | AC | 4,380 ms
60,528 KB |
| testcase_17 | AC | 4,193 ms
59,448 KB |
| testcase_18 | AC | 6,108 ms
59,760 KB |
| testcase_19 | AC | 5,921 ms
60,160 KB |
| testcase_20 | AC | 137 ms
41,432 KB |
ソースコード
package yukicoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
new Main().solver();
// new Q382().trial();
}
void trial() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] d = new int[N - 1];
for (int i = 0; i < N - 1; i++) {
d[i] = sc.nextInt();
}
Arrays.sort(d);
for (int i = 0; i < N - 1; i++) {
System.out.println(d[i]);
}
}
void solver() {
Scanner sc = new Scanner(System.in);
long S = sc.nextLong();
long Start = System.currentTimeMillis();
Graph g = set_edge(S);
Pair p = ms(g);
int n = g.n;
if (p.cardinality == n) {
System.out.println(-1);
} else {
System.out.println((p.cardinality + 1));
boolean f = false;
for (int i = 0; i < p.choosed_vertices.length; i++) {
if (p.choosed_vertices[i]) {
System.out.print((!f ? "" : " ") + (i + 1));
f = true;
}
}
System.out.println();
}
long T = System.currentTimeMillis();
System.err.println((T - Start) + "ms");
}
final long MOD = 1000003;
Graph set_edge(long S) {
S = (S * 12345) % MOD;
int N = (int) (S % 120) + 2;
Graph g = new Graph(N);
S = (S * 12345) % MOD;
long P = S;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
S = (S * 12345) % MOD;
if (S >= P) {
g.set_edge(i, j);
}
}
}
return g;
}
// 無向グラフ
class Graph {
ArrayList<Integer>[] e;
int n;
int[] deg;
boolean[] valid_vertices;// 選ぶことのできる頂点
boolean[] choosed_vertices;// 選ばれた頂点
Graph(int n) {
this.n = n;
deg = new int[n];
valid_vertices = new boolean[n];
choosed_vertices = new boolean[n];
Arrays.fill(valid_vertices, true);
e = new ArrayList[n];
for (int i = 0; i < n; i++) {
e[i] = new ArrayList<>();
}
}
// 無向グラフの辺a<->を作成
void set_edge(int a, int b) {
if (!e[a].contains((Integer) b)) {
e[a].add(b);
e[b].add(a);
deg[a]++;
deg[b]++;
}
}
// 辺a<->bを消去
void delete_undirected_edge(int a, int b) {
e[a].remove((Integer) b);
e[b].remove((Integer) a);
deg[a]--;
deg[b]--;
}
// 頂点vを消去
void delete_vertice(int v) {
while (e[v].size() > 0) {
int u = e[v].get(0);
delete_undirected_edge(u, v);
}
valid_vertices[v] = false;
}
// 頂点vと、vの隣接頂点を消去
void delete_v_with_neighbours(int v) {
while (e[v].size() > 0) {
int u = e[v].get(0);
delete_vertice(u);
}
delete_vertice(v);
}
// deep copy
Graph copy() {
Graph g = new Graph(this.n);
for (int i = 0; i < n; i++) {
g.deg[i] = deg[i];
}
for (int i = 0; i < n; i++) {
g.valid_vertices[i] = valid_vertices[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < e[i].size(); j++) {
(g.e[i]).add(e[i].get(j));
}
}
return g;
}
}
Pair ms(Graph g) {
int[] deg = g.deg;
ArrayList<Integer>[] e = g.e;
boolean[] valid_vertices = g.valid_vertices;
int n = g.n;
int A = -1;// 最も次数の小さい頂点
int B = -1;// Aにつながる頂点のうち最も次数の大きいもの
int deg_me_min = Integer.MAX_VALUE / 4;
int deg_to_max = -Integer.MAX_VALUE / 4;
for (int i = 0; i < n; i++) {
if (!valid_vertices[i])
continue;
if (deg[i] < deg_me_min) {
A = i;
deg_me_min = deg[A];
if (deg_me_min <= 1) {
g.delete_v_with_neighbours(A);
Pair p = ms(g);
p.choosed_vertices[A] = true;
p.cardinality++;
return p;
}
B = e[A].get(0);
deg_to_max = deg[B];
for (int j = 1; j < e[A].size(); j++) {
int u = e[A].get(j);
if (deg[u] > deg_to_max) {
B = u;
deg_to_max = deg[B];
}
}
} else if (deg[i] == deg_me_min) {
for (int j = 0; j < e[A].size(); j++) {
int u = e[A].get(j);
if (deg[u] > deg_to_max) {
A = i;
B = u;
deg_to_max = deg[B];
}
}
}
}
if (A == -1 && B == -1)
return new Pair(0, new boolean[n]);
if (A == -1 || B == -1)
throw new AssertionError("A==-1||B==-1");
if (deg[A] > deg[B])
throw new AssertionError("deg[A]>deg[B]");
if (deg[A] == 2) {
int B2 = -1;
if(e[A].size()!=2)
throw new AssertionError("e[A].size!=2");
if(e[A].get(0)!=B){
B2=e[A].get(0);
}else if(e[A].get(1)!=B){
B2=e[A].get(1);
}else{
throw new AssertionError();
}
for(int i=0;i<e[B2].size();i++){
int u=e[B2].get(i);
if(u==B){
g.delete_v_with_neighbours(A);
Pair p=ms(g);
p.cardinality++;
p.choosed_vertices[A]=true;
return p;
}
}
}
if (deg[A] == 3) {
Graph g2 = g.copy();
g2.delete_v_with_neighbours(A);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[A] = true;
ArrayList<Integer> d = new ArrayList<>();
for (int i = 0; i < e[A].size(); i++) {
d.add(e[A].get(i));
}
g.delete_vertice(A);
Pair p1 = ms2(g, A, 0, d);
return pair_bigger(p1, p2);
}
else if (dominance(B, A, g)) {
g.delete_vertice(B);
Pair p = ms(g);
p.cardinality++;
p.choosed_vertices[B] = true;
return p;
}
Graph g2 = g.copy();
g2.delete_v_with_neighbours(B);
g.delete_vertice(B);
Pair p1 = ms(g);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[B] = true;
if (p1.cardinality > p2.cardinality) {
return p1;
} else {
return p2;
}
}
// 頂点vの隣接頂点から少なくとも二つ使う場合を考える。
// count==1なら2回目
// count==0なら1回目
Pair ms2(Graph g, int v, int count, ArrayList<Integer> neighbour) {
int[] deg = g.deg;
ArrayList<Integer>[] e = g.e;
boolean[] valid_vertices = g.valid_vertices;
int n = g.n;
Pair p = new Pair(0, new boolean[n]);
while (!neighbour.isEmpty()) {
int u = neighbour.get(0);
if (!valid_vertices[u]) {
if (!neighbour.remove((Integer) u)) {
throw new AssertionError("neighbour dosent have u");
}
if (count == 0)
throw new AssertionError("error");
continue;
}
if (deg[u] <= 1) {
g.delete_v_with_neighbours(u);
if (!neighbour.remove((Integer) u)) {
throw new AssertionError("neighbour dosent have u");
}
if (count == 0) {
Pair p1 = ms2(g, v, (count + 1), neighbour);
p1.choosed_vertices[u] = true;
p1.cardinality++;
return p1;
} else if (count == 1) {
Pair p1 = ms(g);
p1.choosed_vertices[u] = true;
p1.cardinality++;
return p1;
} else {
throw new AssertionError("error");
}
}
Graph g2 = g.copy();
g2.delete_v_with_neighbours(u);
if (!neighbour.remove((Integer) u)) {
throw new AssertionError("neighbour dosent have u");
}
if (count == 0) {
Pair p2 = ms2(g2, v, (count + 1), neighbour);
p2.choosed_vertices[u] = true;
p2.cardinality++;
p = pair_bigger(p, p2);
} else if (count == 1) {
Pair p2 = ms(g2);
p2.choosed_vertices[u] = true;
p2.cardinality++;
p = pair_bigger(p, p2);
} else {
throw new AssertionError("error");
}
}
if (neighbour.size() != 0) {
throw new AssertionError("neighbour.size()==" + neighbour.size());
}
return p;
}
Pair pair_bigger(Pair p1, Pair p2) {
return p1.cardinality > p2.cardinality ? p1 : p2;
}
class Pair {
int cardinality;
boolean[] choosed_vertices;
Pair(int cardinality, boolean[] choosed_vertices) {
this.cardinality = cardinality;
this.choosed_vertices = choosed_vertices;
}
}
// whethere N(B)&B is subset of N(A)&A or not;
boolean dominance(int A, int B, Graph g) {
Set<Integer>as = new HashSet<>();
Set<Integer> bs = new HashSet<>();
ArrayList<Integer>[] e = g.e;
for (int i = 0; i < e[A].size(); i++) {
as.add(e[A].get(i));
}
for (int i = 0; i < e[B].size(); i++) {
bs.add(e[B].get(i));
}
if (!as.contains(B)) {
as.add(B);
}
if (!bs.contains(A)) {
bs.add(A);
}
if (as.size() < bs.size())
return false;
for (Iterator<Integer> it = bs.iterator(); it.hasNext();) {
if (!as.contains(it.next())) {
return false;
}
}
return true;
}
}