Contest Duration: - (local time) (120 minutes) Back to Home

Submission #9423384

Source Code Expand

Copy
```import sys

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
for x,y in zip(B, B[1:]):
if A[x] == y:
return False
return True

def solve_small(cand, A, ng_first = -1):
for p in itertools.permutations(cand):
if p[0] == ng_first:
continue
if test(A, p):
return p
return False

if N <= 6:
p = solve_small(range(N), A)
if not p:
print(-1)
exit()
print(' '.join(str(x+1) for x in p))
exit()

in_deg = [0] * (N+10)
for x in A:
in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
B = []
ng = ng_first
while len(rest) >= 4:
x = rest[0]; y = rest[1]
if ng == x:
B.append(y)
rest.popleft()
rest.popleft()
rest.appendleft(x)
else:
B.append(x)
rest.popleft()
ng = A[B[-1]]
return B

rest = deque(range(N))
B = []
prev = N
n = N
for _ in range(N-4):
while q[0] not in se:
heappop(q)
if -q[0][0] == n - 1:
v = q[0][1]
B.append(v)
rest.remove(v)
B += greedy(rest, A, A[B[-1]])
break
x = rest[0]; y = rest[1]
if A[prev] == x:
B.append(y)
rest.popleft()
rest.popleft()
rest.appendleft(x)
else:
B.append(x)
rest.popleft()
prev = B[-1]
v = A[B[-1]]
se.remove((-in_deg[v],v))
in_deg[v] -= 1
n -= 1
if len(B) < N:
B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))```

#### Submission Info

Submission Time 2020-01-11 21:04:03+0900 D - Arrangement maspy Python (3.4.3) 800 2051 Byte AC 408 ms 40016 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
 AC × 3
 AC × 50
Set Name Test Cases
Sample sample_01, sample_02, sample_03
All hand2_01, hand2_02, hand2_03, hand2_04, hand_01, hand_02, hand_03, hand_04, handmaid_01, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, sample_01, sample_02, sample_03, small_01, small_02, small_03, small_04, small_05, special2_01, special2_02, special2_03, special2_04, special2_05, special2_06, special2_07, special2_08, special2_09, special2_10, special_01, special_02, special_03
Case Name Status Exec Time Memory
hand2_01 AC 20 ms 3316 KB
hand2_02 AC 21 ms 3316 KB
hand2_03 AC 174 ms 34364 KB
hand2_04 AC 170 ms 34332 KB
hand_01 AC 21 ms 3316 KB
hand_02 AC 20 ms 3316 KB
hand_03 AC 378 ms 37204 KB
hand_04 AC 372 ms 37844 KB
handmaid_01 AC 21 ms 3316 KB
max_01 AC 408 ms 35924 KB
max_02 AC 314 ms 40016 KB
max_03 AC 273 ms 38484 KB
max_04 AC 399 ms 35924 KB
max_05 AC 336 ms 33744 KB
random_01 AC 21 ms 3316 KB
random_02 AC 21 ms 3316 KB
random_03 AC 21 ms 3316 KB
random_04 AC 20 ms 3316 KB
random_05 AC 21 ms 3316 KB
random_06 AC 21 ms 3316 KB
random_07 AC 20 ms 3316 KB
random_08 AC 21 ms 3316 KB
random_09 AC 20 ms 3316 KB
random_10 AC 20 ms 3316 KB
random_11 AC 21 ms 3316 KB
random_12 AC 20 ms 3316 KB
random_13 AC 21 ms 3316 KB
random_14 AC 21 ms 3316 KB
random_15 AC 21 ms 3316 KB
sample_01 AC 21 ms 3316 KB
sample_02 AC 20 ms 3316 KB
sample_03 AC 21 ms 3316 KB
small_01 AC 21 ms 3316 KB
small_02 AC 21 ms 3316 KB
small_03 AC 21 ms 3316 KB
small_04 AC 20 ms 3316 KB
small_05 AC 20 ms 3316 KB
special2_01 AC 174 ms 34364 KB
special2_02 AC 175 ms 34364 KB
special2_03 AC 187 ms 34364 KB
special2_04 AC 171 ms 34364 KB
special2_05 AC 176 ms 34364 KB
special2_06 AC 193 ms 34620 KB
special2_07 AC 194 ms 35004 KB
special2_08 AC 182 ms 34364 KB
special2_09 AC 200 ms 34876 KB
special2_10 AC 191 ms 34620 KB
special_01 AC 21 ms 3316 KB
special_02 AC 35 ms 5104 KB
special_03 AC 342 ms 34388 KB