Submission #1326248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326248		pramad712	사육제 (CEOI14_carnival)	Pypy 3	100 / 100	201 ms	51000 KiB

carnival

def main():
    length = int(input())
    values = list(range(1, length + 1))

    graph = [[] for _ in range(length + 1)]
    colors = [-1 for _ in range(length + 1)]

    next_color = 1

    print(length, *values, flush=True)
    whole_distinct = int(input())

    while len(values) > 1:
        node = values.pop()
        left, right = 0, len(values) - 1

        print(right - left + 1, *values, flush=True)
        remaining_distinct = int(input())

        if whole_distinct != remaining_distinct:
            colors[node] = next_color
            next_color += 1

            whole_distinct = remaining_distinct
            continue

        whole_distinct = remaining_distinct

        while left < right:
            middle = (left + right) // 2

            print(middle - left + 2, node, *values[left: middle + 1], flush=True)
            whole_guess_distinct = int(input())

            print(middle - left + 1, *values[left: middle + 1], flush=True)
            guess_distinct = int(input())

            if whole_guess_distinct != guess_distinct:
                left = middle + 1
                continue

            right = middle

        graph[node].append(values[left])
        graph[values[left]].append(node)

    colors[values[0]] = next_color

    visited = [False for _ in range(length + 1)]

    for node in range(1, length + 1):
        if visited[node] or colors[node] == -1:
            continue

        color = colors[node]

        dfs = [node]

        while dfs:
            node = dfs.pop()

            visited[node] = True
            colors[node] = color

            for adjacent in graph[node]:
                if visited[adjacent]:
                    continue

                dfs.append(adjacent)

    print(0, *colors[1:], flush=True)
    return 0

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'carnival.py'...

=======
  adding: __main__.pyc (deflated 48%)

=======

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20