Yukicoder No.282 おもりと天秤(2)

これを奇遇転置と呼ぶのはeditorialを見て知った。

solution

奇偶転置ソートをする。 $0, 1, \dots, n-1$から始めて、隣接する$2$項をまとめて$\frac{N}{2}$個比較してswapを$N$回繰り返す。

implementation

#!/usr/bin/env python3
import sys
QUERY_LIMIT = 2000
n = int(input())
a = list(range(1,n+1))
for i in range(QUERY_LIMIT):
    q = []
    j = i % 2
    while j+1 < n:
        q += [a[j], a[j+1]]
        j += 2
    while len(q)//2 < n:
        q += [0, 0]
    print('?', *q)
    sys.stdout.flush()
    q = input().split()
    j = i % 2
    modified = False
    while j+1 < n:
        if q[j//2] == '>':
            a[j], a[j+1] = a[j+1], a[j]
            modified = True
        j += 2
    if not modified:
        break
print('!', *a)