結果

問題 No.382 シャイな人たち (2)
ユーザー nagissnagiss
提出日時 2020-10-12 05:31:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,965 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 83,456 KB
最終ジャッジ日時 2024-07-20 17:54:20
合計ジャッジ時間 18,838 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_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_)
        self.cans = 1  # 最大クリークを構成する集合  # 復元するときはこれを使う
        self.ans = 1
        self._dfs()
        return self.ans

    def _dfs(self):
        E_sorted = self.E_sorted
        elem_num = 0
        recursive_stk = [(0, (1<<self.n)-1)]
        while recursive_stk:
            state = recursive_stk.pop()
            phase = state[0]
            if phase == 0:
                _, candi = state
                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:
                    elem_num -= 1
                    continue
                pivot = (candi & -candi).bit_length() - 1  # 候補から頂点をひとつ取り出す
                smaller_candi = candi & ~E_sorted[pivot]  # pivot と直接結ばれていない頂点の集合（自己ループの無いグラフなので pivot を含む）
                phase = 1
                state = 1, candi, potential, pivot, smaller_candi
            if phase == 1:
                _, candi, potential, pivot, smaller_candi = state
                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
                        elem_num += 1
                        recursive_stk.append((1, candi, potential, pivot, smaller_candi))
                        recursive_stk.append((0, candi & E_sorted[next]))
                        break
                else:
                    elem_num -= 1


def main():
    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])

main()
0