結果

問題 No.382 シャイな人たち (2)
ユーザー uwiuwi
提出日時 2016-08-12 00:39:31
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,455 ms / 8,000 ms
コード長 10,384 bytes
コンパイル時間 5,125 ms
コンパイル使用メモリ 88,916 KB
実行使用メモリ 59,032 KB
最終ジャッジ日時 2024-04-25 02:21:52
合計ジャッジ時間 48,402 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,306 ms
57,660 KB
testcase_01 AC 2,193 ms
58,188 KB
testcase_02 AC 2,455 ms
58,420 KB
testcase_03 AC 1,797 ms
57,536 KB
testcase_04 AC 1,815 ms
57,764 KB
testcase_05 AC 2,013 ms
59,032 KB
testcase_06 AC 2,393 ms
57,804 KB
testcase_07 AC 1,931 ms
57,544 KB
testcase_08 AC 2,418 ms
57,524 KB
testcase_09 AC 2,253 ms
57,480 KB
testcase_10 AC 1,784 ms
57,448 KB
testcase_11 AC 1,963 ms
58,376 KB
testcase_12 AC 1,885 ms
57,524 KB
testcase_13 AC 1,949 ms
57,536 KB
testcase_14 AC 1,742 ms
58,100 KB
testcase_15 AC 1,647 ms
57,736 KB
testcase_16 AC 2,126 ms
57,564 KB
testcase_17 AC 1,375 ms
58,060 KB
testcase_18 AC 1,572 ms
58,224 KB
testcase_19 AC 1,722 ms
57,732 KB
testcase_20 AC 53 ms
36,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)); }
}
0