結果

問題 No.382 シャイな人たち (2)
コンテスト
ユーザー nagiss
提出日時 2020-10-12 04:09:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,128 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 98,432 KB
最終ジャッジ日時 2024-07-20 17:53:15
合計ジャッジ時間 19,208 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class MaxClique:
    # 最大クリーク
    # Bron–Kerbosch algorithm (O(1.4422^|V|)) の枝刈りをしたもの
    # 参考: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/2691674
    # 検証1: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/7620028
    # 検証2: https://judge.yosupo.jp/submission/12486
    def __init__(self, n):
        self.n = n
        self.E = [0] * n
        self.stk = [0] * n  # 最大クリークが入るスタック

    def __repr__(self):
        return "\n".join("{:0{}b}".format(e, self.n) for e in self.E)

    def add_edge(self, v, u):
        # assert v != u
        self.E[v] |= 1 << u
        self.E[u] |= 1 << v

    def invert(self):
        # 補グラフにする
        n, E = self.n, self.E
        mask = (1<<n) - 1  # 正の数にしないと popcount がバグる
        for i in range(n):
            E[i] = ~E[i] & (mask ^ 1<<i)  # 自己ループがあるとバグる

    def solve(self):
        n, E = self.n, self.E
        deg = [bin(v).count("1") for v in E]
        self.index = index = sorted(range(n), key=lambda x: deg[x], reverse=True)  # 頂点番号を次数の降順にソート
        self.E_sorted = E_sorted = []  # E を 次数の降順に並び替えたもの
        for v in index:
            E_sorted_ = 0
            E_v = E[v]
            for i, u in enumerate(index):
                if E_v >> u & 1:
                    E_sorted_ |= 1 << i
            E_sorted.append(E_sorted_)
        cand = (1 << n) - 1  # 候補の集合
        self.cans = 1  # 最大クリークを構成する集合  # 復元するときはこれを使う
        self.ans = 1
        self._dfs(0, cand)
        return self.ans

    def _dfs(self, elem_num, candi):
        if self.ans < elem_num:
            self.ans = elem_num
            cans_ = 0
            index = self.index
            for s in self.stk[:elem_num]:
                cans_ |= 1 << index[s]
            self.cans = cans_
        potential = elem_num + bin(candi).count("1")
        if potential <= self.ans:
            return
        E_sorted = self.E_sorted
        pivot = (candi & -candi).bit_length() - 1  # 候補から頂点をひとつ取り出す
        smaller_candi = candi & ~E_sorted[pivot]  # pivot と直接結ばれていない頂点の集合（自己ループの無いグラフなので pivot を含む）
        while smaller_candi and potential > self.ans:
            next = smaller_candi & -smaller_candi
            candi ^= next
            smaller_candi ^= next
            potential -= 1
            next = next.bit_length() - 1
            if next == pivot or smaller_candi & E_sorted[next]:
                self.stk[elem_num] = next
                self._dfs(elem_num + 1, candi & E_sorted[next])


mod = 1000003
S = int(input())
S = S * 12345 % mod
N = S % 120 + 2
S = S * 12345 % mod
P = S
mc = MaxClique(N)
for i in range(N):
    for j in range(i+1, N):
        S = S * 12345 % mod
        if S < P:
            mc.add_edge(i, j)
ans = mc.solve() + 1
print(ans)
print(*[i+1 for i in range(N) if mc.cans>>i&1])
0