結果
| 問題 |
No.382 シャイな人たち (2)
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2016-08-13 19:53:19 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 680 ms / 8,000 ms |
| コード長 | 11,830 bytes |
| コンパイル時間 | 4,662 ms |
| コンパイル使用メモリ | 90,424 KB |
| 実行使用メモリ | 47,392 KB |
| 最終ジャッジ日時 | 2024-11-07 16:30:05 |
| 合計ジャッジ時間 | 18,084 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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_2 {
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;
int m = (n>>>6)+1;
long[][] g = new long[n][m];
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
S = S * 12345 % 1000003;
if(S < p){
g[i][j>>>6] |= 1L<<j;
g[j][i>>>6] |= 1L<<i;
}
}
}
int[] res = MCS(g);
if(2 <= res.length+1 && res.length+1 <= n){
out.println(res.length+1);
for(int i = 0;i < res.length;i++){
if(i > 0)out.print(" ");
out.print(res[i]+1);
}
out.println();
}else{
out.println(-1);
}
}
public static int[] MCS(long[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
long[] Qmax = new long[m];
int[] no = new int[n];
int[] V = new int[n];
extendedInitialSortNumber(V, no, Qmax, g);
long[] nQmax = new long[m];
for(int i = 0;i < n;i++)if(Qmax[V[i]>>>6]<<~V[i]<0)nQmax[i>>>6] |= 1L<<i;
int[] nno = new int[n];
for(int i = 0;i < n;i++)nno[i] = no[V[i]];
long[][] ng = new long[n][m];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(g[V[i]][V[j]>>>6]<<~V[j]<0){
ng[i][j>>>6] |= 1L<<j;
}
}
}
long[] nv = new long[m];
fill(nv, n);
int[] nr = new int[n];
for(int i = 0;i < n;i++)nr[i] = i;
expandS(nv, nr, nno, new long[m], Qmax, ng);
int[] rec = reconstruct(Qmax, V);
// check(rec, g);
return rec;
// return size(Qmax);
}
private static int[] reconstruct(long[] Qmax, int[] V)
{
int m = size(Qmax);
int[] ret = new int[m];
int p = 0;
for(int i = 0;i < Qmax.length;i++){
for(long j = Qmax[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
ret[p++] = V[id];
}
}
assert p == m;
Arrays.sort(ret);
return ret;
}
private static void fill(long[] a, int n)
{
for(int i = 0;i < a.length && i < n>>>6;i++){
a[i] = -1L;
}
if((n&63) != 0)a[n>>>6] = (1L<<n)-1;
}
private static void check(int[] s, long[][] g)
{
for(int i = 0;i < s.length;i++){
for(int j = i+1;j < s.length;j++){
if(g[s[i]][s[j]>>>6]<<~s[j]>=0)throw new RuntimeException(s[i] + " " + s[j]);
}
}
}
static void expandS(long[] Va, int[] R, int[] no, long[] Q, long[] Qmax, long[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
for(int j = R.length-1;j >= 0;j--){
int p = R[j];
assert no[p] >= 1;
if(size(Q) + no[p] > size(Qmax)){
Q[p>>>6] |= 1L<<p;
long[] Vp = new long[Va.length];
for(int k = 0;k < m;k++){
Vp[k] = Va[k]&g[p][k];
}
if(!empty(Vp)){
int[] newR = new int[size(Vp)];
int[] newNo = new int[n];
int k = renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q));
newR = Arrays.copyOfRange(newR, k, newR.length);
expandS(Vp, newR, newNo, Q, Qmax, g);
}else if(size(Q) > size(Qmax)){
for(int k = 0;k < Qmax.length;k++){
Qmax[k] = Q[k];
}
}
Q[p>>>6] ^= 1L<<p;
Va[p>>>6] ^= 1L<<p;
}
}
}
private static void ReNUMBER(int p, int[] no, int nop, int noth, long[][] c, long[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
for(int k1 = 1;k1 <= noth-1;k1++){
int inter = 0;
int q = -1;
for(int i = 0;i < m;i++){
long inte = g[p][i]&c[k1][i];
int icb = Long.bitCount(inte);
inter += icb;
if(inter >= 2)break;
if(icb == 1){
q = Long.numberOfTrailingZeros(inte)|i<<6;
}
}
if(inter == 1){
assert q != -1;
inner:
for(int k2 = k1 + 1;k2 <= noth;k2++){
for(int i = 0;i < m;i++){
if((g[q][i]&c[k2][i]) != 0)continue inner;
}
no[q] = k2;
no[p] = k1;
assert p != q;
assert c[nop][p>>>6]<<~p<0;
assert c[k1][p>>>6]<<~p>=0;
assert c[k1][q>>>6]<<~q<0;
assert c[k2][q>>>6]<<~q>=0;
c[nop][p>>>6] ^= 1L<<p;
c[k1][p>>>6] ^= 1L<<p;
c[k1][q>>>6] ^= 1L<<q;
c[k2][q>>>6] ^= 1L<<q;
return;
}
}
}
}
// in: Va, noth
// out: R,no
private static int renumberSort(long[] Va, int[] R, int[] no, long[][] g, int noth)
{
Arrays.fill(R, -1);
Arrays.fill(no, -1);
int n = g.length;
int m = (n>>>6)+1;
int maxno = 0;
long[][] c = new long[size(Va)+1][m];
for(int z = 0;z < m;z++){
for(long y = Va[z];y != 0;y&=y-1){
int p = Long.numberOfTrailingZeros(y)|z<<6;
// Conventional greedy approximate coloring
int k = 1;
inner:
while(true){
for(int i = 0;i < m;i++){
if((g[p][i]&c[k][i]) != 0){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
}
no[p] = k;
c[k][p>>>6] |= 1L<<p;
// Re-NUMBER
if(k > noth && k == maxno){
ReNUMBER(p, no, k, noth, c, g);
if(empty(c[maxno])){
maxno--;
}
}
}
}
int i = size(Va);
if(noth < 0)noth = 0;
int k;
for(k = maxno;k >= noth+1;k--){
for(int j = m-1;j >= 0;j--){
for(long y = c[k][j];y != 0;y^=Long.highestOneBit(y)){
int x = j<<6|63-Long.numberOfLeadingZeros(y);
i--;
R[i] = x;
no[R[i]] = k;
}
}
}
if(i != 0){
k--;
inner:
for(int j = m-1;j >= 0;j--){
for(long y = c[k][j];y != 0;y^=Long.highestOneBit(y)){
int x = j<<6|63-Long.numberOfLeadingZeros(y);
i--;
R[i] = x;
no[R[i]] = noth;
break inner;
}
}
}
return i;
}
public static int size(long[] a)
{
int ret = 0;
for(long v : a)ret += Long.bitCount(v);
return ret;
}
public static boolean empty(long[] a)
{
for(long v : a)if(v != 0)return false;
return true;
}
public static int min(long[] a)
{
for(int i = 0;i < a.length;i++){
if(a[i] != 0L)return Long.numberOfTrailingZeros(a[i])|i<<6;
}
return -1;
}
private static void extendedInitialSortNumber(int[] V, int[] no, long[] Qmax, long[][] g)
{
int n = g.length;
int[] degs = new int[n];
int maxdeg = 0;
for(int i = 0;i < n;i++){
degs[i] = size(g[i]);
maxdeg = Math.max(maxdeg, degs[i]);
}
// SORT
long[] R = new long[(n>>>6)+1];
fill(R, n);
int vp = n;
long[] Rmin = rmin(R, degs);
while(size(Rmin) != size(R)){
int p = min(Rmin);
if(size(Rmin) >= 2){
int minv = Integer.MAX_VALUE;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
int lv = exdeg(id, degs, g);
if(lv < minv){
minv = lv;
p = id;
}
}
}
}
V[--vp] = p;
R[p>>>6] ^= 1L<<p;
for(int i = 0;i < R.length;i++){
for(long j = R[i]&g[p][i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
degs[id]--;
}
}
Rmin = rmin(R, degs);
}
// Regular subgraph
numberSort(Rmin, no, g);
int ii = 0;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
V[ii++] = id;
}
}
// NUMBER
NUMBER: {
int m = 0;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
m = Math.max(m, no[id]);
}
}
int mmax = size(Rmin) + maxdeg - m;
m++;
for(int i = size(Rmin);i < mmax;i++){
if(i >= n)break NUMBER;
no[V[i]] = m++;
}
for(int i = mmax;i < n;i++){
no[V[i]] = maxdeg + 1;
}
}
// START
boolean fullm1 = true;
outer:
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
if(degs[id] != size(Rmin)-1){
fullm1 = false;
break outer;
}
}
}
if(fullm1){
for(int i = 0;i < Rmin.length;i++){
Qmax[i] = Rmin[i];
}
}
}
private static int exdeg(int q, int[] degs, long[][] g)
{
int ret = 0;
for(int i = 0;i < g[q].length;i++){
for(long j = g[q][i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
ret += degs[id];
}
}
return ret;
}
private static long[] rmin(long[] R, int[] degs)
{
int mindeg = 9999;
long[] Rmin = new long[R.length];
for(int i = 0;i < R.length;i++){
for(long j = R[i];j != 0;j&=j-1){
int v = Long.numberOfTrailingZeros(j)|i<<6;
if(degs[v] < mindeg){
mindeg = degs[v];
Rmin[v>>>6] |= 1L<<v;
}else if(degs[v] == mindeg){
Arrays.fill(Rmin, 0L);
Rmin[v>>>6] |= 1L<<v;
}
}
}
return Rmin;
}
private static void numberSort(long[] R, int[] no, long[][] g)
{
int n = g.length;
int maxno = 0;
int m = (n>>>6)+1;
long[][] c = new long[size(R)+1][m];
for(int z = 0;z < R.length;z++){
for(long j = R[z];j != 0;j &= j-1){
int p = Long.numberOfTrailingZeros(j)|z<<6;
int k = 1;
inner:
while(true){
for(int i = 0;i < m;i++){
if((g[p][i]&c[k][i]) != 0){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
}
no[p] = k;
c[k][p>>>6] |= 1L<<p;
}
}
// sort
int i = 0;
for(int k = 1;k <= maxno;k++){
for(int u = 0;u < m;u++){
for(long j = c[k][u];j != 0;j &= j-1){
int p = Long.numberOfTrailingZeros(j)|u<<6;
i++;
R[p>>>6] |= 1L<<p;
}
}
}
assert i == size(R);
}
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_2().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)); }
}