結果

問題 No.382 シャイな人たち (2)
ユーザー Min_25Min_25
提出日時 2016-06-19 06:49:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 798 ms / 8,000 ms
コード長 7,012 bytes
コンパイル時間 1,061 ms
コンパイル使用メモリ 85,532 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 05:19:06
合計ジャッジ時間 15,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 798 ms
5,248 KB
testcase_01 AC 776 ms
5,248 KB
testcase_02 AC 656 ms
5,248 KB
testcase_03 AC 619 ms
5,248 KB
testcase_04 AC 629 ms
5,248 KB
testcase_05 AC 648 ms
5,248 KB
testcase_06 AC 583 ms
5,248 KB
testcase_07 AC 714 ms
5,248 KB
testcase_08 AC 573 ms
5,248 KB
testcase_09 AC 586 ms
5,248 KB
testcase_10 AC 604 ms
5,248 KB
testcase_11 AC 652 ms
5,248 KB
testcase_12 AC 568 ms
5,248 KB
testcase_13 AC 640 ms
5,248 KB
testcase_14 AC 612 ms
5,248 KB
testcase_15 AC 655 ms
5,248 KB
testcase_16 AC 563 ms
5,248 KB
testcase_17 AC 487 ms
5,248 KB
testcase_18 AC 710 ms
5,248 KB
testcase_19 AC 680 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <tuple>

#define _fetch(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

using u128 = __uint128_t;

const u32 N_MAX = 120;

int degs[N_MAX + 1];
u128 V_deg[N_MAX + 2];
u128 edges[N_MAX + 1];

inline int ctz(u128 n) {
  if (u64(n)) return __builtin_ctzll(u64(n));
  else return 64 + __builtin_ctzll(u64(n >> 64));
}

inline int pop_count(u128 n) {
  if (u64(n)) return __builtin_popcountll(u64(n)) + __builtin_popcountll(u64(n >> 64));
  else return __builtin_popcountll(u64(n >> 64));
}

inline void delete_v(u128 G, int v) {
  auto Nv = edges[v] & G;
  while (Nv) {
    auto fy = Nv & -Nv;
    int y = ctz(fy);
    V_deg[degs[y]--] ^= fy;
    V_deg[degs[y]] ^= fy;
    Nv ^= fy;
  }
}

inline void insert_v(u128 G, int v) {
  auto Nv = edges[v] & G;
  while (Nv) {
    auto fy = Nv & -Nv;
    int y = ctz(fy);
    V_deg[degs[y]++] ^= fy;
    V_deg[degs[y]] ^= fy;
    Nv ^= fy;
  }
}

inline void delete_V(u128 G, u128 V) {
  while (V) {
    auto fv = V & -V;
    int v = ctz(fv);
    delete_v(G, v);
    V ^= fv;
  }
}

inline void insert_V(u128 G, u128 V) {
  while (V) {
    auto fv = V & -V;
    int v = ctz(fv);
    insert_v(G, v);
    V ^= fv;
  }
}

inline int max_deg_vertex(u128 G, u128 S, int beg) {
  for (int deg = beg; ; ++deg) {
    u128 Vd = V_deg[deg] & G;
    if ((S |= Vd) != G) continue;
    return ctz(Vd & -Vd);
  }
}

bool is_clique(u128 G) {
  auto V = G;
  while (V) {
    auto fv = V & -V;
    int v = ctz(fv);
    auto Nv = fv ^ (edges[v] & G);
    if (Nv != G) return false;
    V ^= fv;
  }
  return true;
}

u128 calc_N2v(u128 G, int v, u128 Nv) {
  auto fv = u128(1) << v;
  auto Nv_back = Nv;
  auto N2v = u128(0);
  while (Nv) {
    auto fy = Nv & -Nv;
    int y = ctz(fy);
    N2v |= edges[y] & G;
    Nv ^= fy;
  }
  return N2v & ~(Nv_back | fv);
}

u128 mirror(u128 G, int v, u128 Nv) {
  auto N2v = calc_N2v(G, v, Nv);
  u128 ret = 0;
  while (N2v) {
    auto fw = N2v & -N2v;
    int w = ctz(fw);
    auto Nw = fw ^ (edges[w] & G);
    auto Nv_Nw = Nv & ~Nw;
    if (is_clique(Nv_Nw)) ret |= fw;
    N2v ^= fw;
  }
  return ret;
}

int vertices[N_MAX];

// Naive: O(3^(n/3)) ~= O(1.4422^n)
int mis1(u128 G) {
  if (G == 0) return 0;
  for (int deg = 0; ; ++deg) if (V_deg[deg] & G) {
    int i_max = 0;
    auto fv = V_deg[deg] & G; fv &= -fv;
    int v = ctz(fv);
    auto Nv = (fv ^ edges[v]) & G;
    while (Nv) {
      auto fy = Nv & -Nv;
      int y = ctz(fy);
      auto Ny = edges[y] & G;
      delete_v(G, y);
      i_max = max(i_max, mis1(G ^ (Ny | fy)));
      insert_v(G, y);
      Nv ^= fy;
    }
    return 1 + i_max;
  }
}

// O(1.2905^n)
int mis3(u128 G, int idx=0) {
  if (G == 0) return 0;

  // d(v) <= 1
  const u128 V01 = (V_deg[0] | V_deg[1]) & G;
  if (V01) {
    auto fv = V01 & -V01;
    int v = ctz(fv);
    auto Nv = edges[v] & G;

    delete_V(G, Nv); vertices[idx] = v;
    int ret = 1 + mis3(G ^ (Nv | fv), idx + 1);
    insert_V(G, Nv);
    return ret;
  }

  int vertices_back[N_MAX];

  // d(v) == 2
  const u128 V2 = V_deg[2] & G;
  if (V2) {
    auto fv = V2 & -V2;
    int v = ctz(fv);
    auto Nv = edges[v] & G;

    auto fu1 = Nv & -Nv; Nv ^= fu1;
    int u1 = ctz(fu1);
    auto fu2 = Nv; Nv ^= fu1;
    int u2 = ctz(fu2);

    auto Nu1 = edges[u1] & G;
    if (Nu1 & fu2) {
      delete_V(G, Nv); vertices[idx] = v;
      int ret = 1 + mis3(G ^ (Nv | fv), idx + 1);
      insert_V(G, Nv);
      return ret;
    } else {
      auto N2v = calc_N2v(G, v, Nv);
      if ((N2v & (N2v - 1)) == 1) {
        auto fw = N2v;
        int w = ctz(fw);
        auto Nw = edges[w] & G;

        delete_V(G, Nv | Nw); vertices[idx] = v; vertices[idx + 1] = w;
        int ret1 = 2 + mis3(G ^ (fv | Nv | fw | Nw), idx + 2);
        copy(vertices + idx, vertices + idx + ret1, vertices_back);
        insert_V(G, Nv | Nw);

        delete_V(G, fw); vertices[idx] = u1; vertices[idx + 1] = u2;
        int ret2 = 2 + mis3(G ^ (fv | Nv | fw), idx + 2);
        insert_V(G, fw);

        if (ret1 > ret2) {
          copy(vertices_back, vertices_back + ret1, vertices + idx);
        }
        return max(ret1, ret2);
      } else {
        delete_V(G, Nv); vertices[idx] = v;
        int ret1 = 1 + mis3(G ^ (fv | Nv), idx + 1); 
        copy(vertices + idx, vertices + idx + ret1, vertices_back);
        insert_V(G, Nv);

        auto Mv = mirror(G, v, Nv);
        delete_V(G, Mv | fv);
        int ret2 = mis3(G ^ (fv | Mv), idx);
        insert_V(G, Mv | fv);

        if (ret1 > ret2) {
          copy(vertices_back, vertices_back + ret1, vertices + idx);
        }
        return max(ret1, ret2);
      }
    }
  }

  // d(v) >= 3
  if (1) {
    int v = max_deg_vertex(G, V2, 3);
    auto fv = u128(1) << v;
    auto Nv = edges[v] & G;

    // G \ v
    delete_v(G, v);
    int ret = mis3(G ^ fv, idx); copy(vertices + idx, vertices + idx + ret, vertices_back);
    insert_v(G, v);

    // G \ N(v)
    delete_V(G, Nv); vertices[idx] = v;
    int ret2 = 1 + mis3(G ^ (Nv | fv), idx + 1);
    insert_V(G, Nv);

    if (ret > ret2) {
      copy(vertices_back, vertices_back + ret, vertices + idx);
    } else {
      ret = ret2;
    }
    return ret;
  }
}

struct Rand {
  Rand(u32 seed) : x(seed) {}
  u32 next() { return x = u64(x) * 12345 % 1000003; }
  u32 x;
};

int gene_graph(int S) {
  auto gene = Rand(S);
  int N = gene.next() % N_MAX + 2;
  int P = gene.next();
  // fprintf(stderr, "N: %u, P: %u\n", N, P);
  rep(i, N) {
    degs[i] = V_deg[i] = edges[i] = 0;
  }
  rep(i, N) rep(j, i + 1, N) {
    int X = gene.next();
    if (X >= P) {
      edges[i] |= u128(1) << j; degs[i]++;
      edges[j] |= u128(1) << i; degs[j]++;
      // fprintf(stderr, "S: %u, E: %u <-> %u (%u)\n", S, i, j, X);
    }
  }
  rep(i, N) V_deg[degs[i]] |= u128(1) << i;
  return N;
}

void solve() {
  int S;
  // clock_t worst = 0;
  while (~scanf("%d", &S)) {
    int N = gene_graph(S);
    auto G = (u128(1) << N) - 1;
    // clock_t beg = clock();
    int len = mis3(G);
    // clock_t end = clock();
    // if (end - beg > worst) {
    //   worst = end - beg;
    //   printf("%u: %d %.3f\n", S, pop_count(G), double(worst) / CLOCKS_PER_SEC);
    // }
    if (len == N) {
      puts("-1");
    } else {
      printf("%u\n", len + 1);
      printf("%u", vertices[0] + 1);
      rep(i, 1, len) printf(" %u", vertices[i] + 1);
      puts("");
    }
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0