/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 34ms 17.238 MiB
#2 Wrong Answer 61ms 18.613 MiB

Code

import sys
input = sys.stdin.readline

def make_perm(N):
    # Special cases
    if N == 1:
        return [1]
    if N <= 4:
        return None   # impossible

    evens = list(range(2, N+1, 2))
    odds  = list(range(1, N+1, 2))

    # Try 4 greedy variants:
    #   start_parity = 0 (even) or 1 (odd)
    #   direction    = +1 (low→high) or -1 (high→low)
    for start_parity in (0, 1):
        for direction in (1, -1):
            used = [False] * (N+1)
            ans  = []
            parity = start_parity
            ok = True

            for _ in range(N):
                placed = False
                arr = evens if parity == 0 else odds
                # depending on direction, choose scan order
                seq = arr if direction == 1 else arr[::-1]

                for x in seq:
                    if used[x]:
                        continue
                    if ans:
                        prev = ans[-1]
                        # forbid |prev−x| ≤ 1,
                        # and forbid even–even adjacency
                        if abs(prev - x) <= 1 or (prev%2 == 0 and x%2 == 0):
                            continue
                    # place x
                    used[x] = True
                    ans.append(x)
                    placed = True
                    break

                if not placed:
                    ok = False
                    break

                parity ^= 1

            if ok and len(ans) == N:
                return ans

    return None

def main():
    T = int(input())
    out = []
    for _ in range(T):
        N = int(input())
        perm = make_perm(N)
        if perm is None:
            out.append("-1")
        else:
            out.append(" ".join(map(str, perm)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Information

Submit By
Type
Submission
Problem
P1203 D. Roy Loves Permutation
Language
PyPy 3 (Python 3.9.18 PyPy 7.3.15)
Submit At
2025-06-09 07:18:58
Judged At
2025-06-09 07:18:58
Judged By
Score
0
Total Time
61ms
Peak Memory
18.613 MiB