結果
| 問題 |
No.382 シャイな人たち (2)
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2016-08-12 00:39:31 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,513 ms / 8,000 ms |
| コード長 | 10,384 bytes |
| コンパイル時間 | 4,619 ms |
| コンパイル使用メモリ | 89,004 KB |
| 実行使用メモリ | 59,576 KB |
| 最終ジャッジ日時 | 2024-11-07 11:53:56 |
| 合計ジャッジ時間 | 47,492 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 |
ソースコード
package q3xx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class N382 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
long S = ni();
S = S * 12345 % 1000003;
int n = (int)(S%120)+2;
S = S * 12345 % 1000003;
int p = (int)S;
boolean[][] g = new boolean[n][n];
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
S = S * 12345 % 1000003;
g[i][j] = g[j][i] = S < p;
}
}
boolean[] res = MCS(g);
if(2 <= size(res)+1 && size(res)+1 <= n){
out.println(size(res)+1);
boolean f = true;
for(int i = 0;i < n;i++){
if(res[i]){
if(!f)out.print(" ");
f = false;
out.print(i+1);
}
}
out.println();
}else{
out.println(-1);
}
}
static boolean[] MCS(boolean[][] g)
{
int n = g.length;
boolean[] Q = new boolean[n];
boolean[] Qmax = new boolean[n];
int[] no = new int[n];
int[] V = new int[n];
extendedInitialSortNumber(V, no, Qmax, g);
int[] f = new int[n];
for(int i = 0;i < n;i++){
f[V[i]] = i;
}
boolean[] nQmax = new boolean[n];
for(int i = 0;i < n;i++)nQmax[f[i]] = Qmax[i];
int[] nno = new int[n];
for(int i = 0;i < n;i++)nno[f[i]] = no[i];
for(int i = 0;i < n;i++)V[i] = i;
boolean[][] ng = new boolean[n][n];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
ng[f[i]][f[j]] = g[i][j];
}
}
// reconstruct
expandS(Arrays.copyOf(V, n), Arrays.copyOf(V, n), nno, Q, Qmax, ng);
boolean[] ret = new boolean[n];
for(int i = 0;i < n;i++){
ret[i] = Qmax[f[i]];
}
return ret;
}
static void extendedInitialSortNumber(int[] V, int[] no, boolean[] Qmax, boolean[][] g)
{
int n = g.length;
int[] degs = new int[n];
int maxdeg = 0;
for(int i = 0;i < n;i++){
int deg = 0;
for(int j = 0;j < n;j++){
if(g[i][j]){
deg++;
}
}
degs[i] = deg;
maxdeg = Math.max(maxdeg, degs[i]);
}
// SORT
int[] R = new int[n];
for(int i = 0;i < n;i++)R[i] = i;
int vp = n;
int[] Rmin = rmin(R, degs);
while(Rmin.length != R.length){
int p = Rmin[0];
if(Rmin.length >= 2){
int minv = exdeg(Rmin[0], degs, g);
for(int i = 1;i < Rmin.length;i++){
int lv = exdeg(Rmin[i], degs, g);
if(lv < minv){
minv = lv;
p = Rmin[i];
}
}
}
V[--vp] = p;
R = remove(R, p);
for(int j = 0;j < R.length;j++){
if(g[p][R[j]]){
degs[R[j]]--;
}
}
Rmin = rmin(R, degs);
}
// Regular subgraph
numberSort(Rmin, no, g);
for(int i = 0;i < Rmin.length;i++){
V[i] = Rmin[i];
}
// NUMBER
NUMBER: {
int m = 0;
for(int i = 0;i < Rmin.length;i++){
m = Math.max(m, no[Rmin[i]]);
}
int mmax = Rmin.length + maxdeg - m;
m++;
for(int i = Rmin.length;i < mmax;i++){
if(i >= n){
break NUMBER;
}
no[V[i]] = m;
m++;
}
for(int i = mmax;i < n;i++){
no[V[i]] = maxdeg + 1;
}
}
// START
boolean fullm1 = true;
for(int i = 0;i < Rmin.length;i++){
if(degs[Rmin[i]] == Rmin.length-1){
}else{
fullm1 = false;
}
}
if(fullm1){
for(int i = 0;i < Rmin.length;i++){
Qmax[Rmin[i]] = true;
}
}
}
static void numberSort(int[] R, int[] no, boolean[][] g)
{
int n = g.length;
int maxno = 0;
boolean[][] c = new boolean[n+1][n];
for(int p : R){
int k = 1;
inner:
while(true){
for(int i = 0;i < n;i++){
if(g[p][i] && c[k][i]){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
}
no[p] = k;
c[k][p] = true;
}
// sort
int i = 0;
for(int k = 1;k <= maxno;k++){
for(int j = 0;j < n;j++){
if(c[k][j]){
R[i++] = j;
}
}
}
assert i == R.length;
}
static void expandS(int[] Va, int[] R, int[] no, boolean[] Q, boolean[] Qmax, boolean[][] g)
{
int n = g.length;
// U.tr("come", Va, R, no, Q);
for(int j = R.length-1;j >= 0;j--){
int p = R[j];
// U.tr("no", p, Va, R);
assert no[p] >= 1;
if(size(Q) + no[p] > size(Qmax)){
Q[p] = true;
int[] Vp = new int[Va.length];
int vpp = 0;
// U.tr("gp", g[p]);
for(int k = 0;k < Va.length;k++){
if(g[p][Va[k]]){
Vp[vpp++] = Va[k];
}
}
if(vpp > 0){
int[] newR = new int[vpp];
Arrays.fill(newR, -1);
int[] newNo = new int[n];
Vp = Arrays.copyOf(Vp, vpp);
renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q));
int k = 0;
for(;k < newR.length && newR[k] == -1;k++);
newR = Arrays.copyOfRange(newR, k, vpp);
// U.tr("prev", Vp, newR, Qmax, Q);
expandS(Vp, newR, newNo, Q, Qmax, g);
}else if(size(Q) > size(Qmax)){
for(int k = 0;k < n;k++){
Qmax[k] = Q[k];
}
}
Q[p] = false;
Va = removePreservingOrder(Va, p);
}
}
}
static void ReNUMBER(int p, int[] no, int nop, int noth, boolean[][] c, boolean[][] g)
{
int n = g.length;
for(int k1 = 1;k1 <= noth-1;k1++){
int inter = 0;
int q = -1;
for(int i = 0;i < n;i++){
if(g[p][i] && c[k1][i]){
q = i;
if(++inter == 2)break;
}
}
if(inter == 1){
assert q != -1;
inner:
for(int k2 = k1 + 1;k2 <= noth;k2++){
for(int i = 0;i < n;i++){
if(g[q][i] && c[k2][i])continue inner;
}
no[q] = k2;
no[p] = k1;
assert p != q;
assert c[nop][p];
assert !c[k1][p];
assert c[k1][q];
assert !c[k2][q];
c[nop][p] = false;
c[k1][p] = true;
c[k1][q] = false;
c[k2][q] = true;
return;
}
}
}
}
// in: Va, noth
// out: R,no
static void renumberSort(int[] Va, int[] R, int[] no, boolean[][] g, int noth)
{
Arrays.fill(R, -1);
Arrays.fill(no, -1);
int n = g.length;
int maxno = 0;
boolean[][] c = new boolean[Va.length+1][n];
for(int p : Va){
// Conventional greedy approximate coloring
int k = 1;
inner:
while(true){
for(int i = 0;i < n;i++){
if(g[p][i] && c[k][i]){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
}
no[p] = k;
c[k][p] = true;
// Re-NUMBER
if(k > noth && k == maxno){
ReNUMBER(p, no, k, noth, c, g);
if(empty(c[maxno])){
maxno--;
}
}
}
int i = Va.length;
if(noth < 0)noth = 0;
// U.tr("noth", noth);
// for(int k = 1;k <= maxno;k++){
// UTr.tf(c[k]);
// }
int k;
for(k = maxno;k >= noth+1;k--){
for(int j = n-1;j >= 0;j--){
if(c[k][j]){
i--;
R[i] = j;
no[R[i]] = k;
}
}
}
if(i != 0){
k--;
for(int j = n-1;j >= 0;j--){
if(c[k][j]){
i--;
R[i] = j;
no[R[i]] = noth;
break;
}
}
}
}
static int[] remove(int[] a, int v)
{
for(int i = 0;i < a.length;i++){
if(a[i] == v){
a[i] = a[a.length-1];
return Arrays.copyOf(a, a.length-1);
}
}
throw new RuntimeException();
}
static int[] removePreservingOrder(int[] a, int v)
{
for(int i = 0;i < a.length;i++){
if(a[i] == v){
for(int j = i+1;j < a.length;j++){
a[i] = a[j];
}
return Arrays.copyOf(a, a.length-1);
}
}
throw new RuntimeException();
}
static int exdeg(int q, int[] degs, boolean[][] g)
{
int ret = 0;
for(int i = 0;i < g.length;i++){
if(g[q][i]){
ret += degs[i];
}
}
return ret;
}
static int[] rmin(int[] R, int[] degs)
{
int mindeg = 9999;
int[] Rmin = new int[R.length];
int rminp = 0;
for(int v : R){
if(degs[v] < mindeg){
mindeg = degs[v];
Rmin[rminp++] = v;
}else if(degs[v] == mindeg){
rminp = 0;
Rmin[rminp++] = v;
}
}
Rmin = Arrays.copyOf(Rmin, rminp);
return Rmin;
}
static boolean empty(boolean[] v)
{
for(boolean b : v)if(b)return false;
return true;
}
static int size(boolean[] v)
{
int ret = 0;
for(boolean b : v)if(b)ret++;
return ret;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new N382().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}