Submission #46691785

---

Source Code Expand

import random
from collections import defaultdict
N, D, Q = map(int, input().split())
remainQ = Q

# 30≤N≤100

# なんとなくの重さの順序付けをして初期配置を決める処理 Nは最大100
# weights = [1,5,3,7,89,2,90] # 実際には見えない裏に持ってるお土産ごとの重さ
# N = len(weights)
# D = 3

def compare_single(g1, g2):
    # 1個ずつ比較
    global remainQ
    print(1, 1, g1, g2, flush=True)
    remainQ -= 1
    ret = input()
    # todo イコール対策
    if ret == "=":
        ret = "<"
    return ret

def compare_group(g1, g2, dict_idx):
    global remainQ
    print(len(dict_idx[g1]), len(dict_idx[g2]), *dict_idx[g1], *dict_idx[g2], flush=True)
    remainQ -= 1
    return input()

def create_tree(par:list, idxs:list)->int:
    """
    idxs親を求めるインデックス一覧
    root 新しくできたindex
    """
    # 親配列初期化
    for idx in idxs:
        par[idx]= -1
    left = idxs[0]
    for right in idxs[1:]:
        ret = compare_single(left, right)
        if ret == "<":
            par[left] = right
            left = right
        else:
            par[right] = left
    par[left] = -1
    return left
def get_nodes(par:list, root:int)->list:
    """
    rootに繋がってる要素一覧取得
    """
    indices = [index for index, item in enumerate(par) if item == root]
    return indices

def init_desc_groups(thr:int):
    """
    残り回数thrを切るまで単純比較して、ある程度傾斜をつけた初期配列を取得する
    """
    par = [-1]*N # 親配列
    nodes = list(range(N))#最初は全部親がわからない
    desc_list = []#暫定降順配列

    for _ in range(N):
        if len(nodes) == 1:
            root = nodes[0]
            par[root] = -1
        else:
            root = create_tree(par,nodes)
        desc_list.append(root)
        nodes = get_nodes(par, root)
        # print(root,par,nodes)
        if (Q - remainQ) >= thr:
            break
        if len(desc_list) == MAX_SELECT:
            break
    # print(root,par,desc_list)

    # 降順リストに入らなかったものを混ぜる
    unknown = list(range(N))
    for v in desc_list:
        unknown.remove(v)
    random.shuffle(unknown)
    omiyage = desc_list + unknown
    ans = [-1]*N
    tmp = (list(range(D)) + list(range(D-1,-1,-1)))*50#最低でも100にする
    tmp = tmp[:N]

    for i, idx in enumerate(omiyage):
        # ans[idx] = i%D
        ans[idx] = tmp[i]
    return ans

def move_random_rollback(ans):
    dict_idx = defaultdict(list)
    for i, v in enumerate(ans):
        dict_idx[v].append(i)

    while remainQ:
        # どの集合を調整するか選ぶ
        g1, g2 = random.sample(range(D), 2) 
        # Interactive
        ret = compare_group(g1, g2, dict_idx)
        if ret == "=": continue
        # g1のほうが大きいようにする
        if ret == "<":
            g1, g2 = g2, g1
        # G1からG2に移動させる
        if len(dict_idx[g1]) == 1: continue
        while remainQ:
            item = random.choice(dict_idx[g1])
            dict_idx[g1].remove(item)
            dict_idx[g2].append(item)
            ret = compare_group(g1, g2, dict_idx)
            if ret == ">":
                ans[item] = g2 # 移動を確定させる
                if len(dict_idx[g1]) == 1:
                    break
            elif ret == "=":
                ans[item] = g2 # 移動を確定させる
                break
            else:
                if remainQ > yakinamashiT and random.randint(1,100) >= yakinamashiR: 
                    ans[item] = g2 # 移動を確定させる
                else:
                    dict_idx[g1].append(item)
                    dict_idx[g2].remove(item)
                break
    return ans

THR = Q//3 #残り回数thr回を割ったらやめる
MAX_SELECT = D*2 # 最大何個降順で引っ張る？
yakinamashiT = 400 # 残り回数なん回まで焼きなまし適用させるか
yakinamashiR = 95 # 焼きなましするときの、悪い交換を許容する確率
# 順番初期配列
# ans = [None]*N
# ans = [i%D for i in range(N)] # random split

# 降順初期配列
ans = init_desc_groups(THR)

ans = move_random_rollback(ans)
print(*ans)

Submission Info

Judge Result