#1189222 (PyPy3) No.3735 Offbeat Permutation Tree

• 問題: No.3735 Offbeat Permutation Tree
• ユーザー: Kurao
• 提出日時: 2026-09-19 17:06:32
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 450 ms / 2,000 ms
• コード長: 5,566 bytes
• コンパイル時間: 67 ms
• コンパイル使用メモリ: 83,280 KB
• 実行使用メモリ: 161,480 KB
• 最終ジャッジ日時: 2026-09-19 17:06:58
• 合計ジャッジ時間: 11,122 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 35

ソースコード

from __future__ import annotations
import sys
sys.setrecursionlimit(2*10**7)
#↓codon===============================
import string
Alp_low=list(string.ascii_lowercase)
Alp_up=list(string.ascii_uppercase)
Digit="0123456789"
dij=[[0,1],[1,0],[0,-1],[-1,0]]
def nin():
    return list(map(int,input().split()))
def deq(x):
    return [i-1 for i in x]
mod=998244353
_factorial=[1]
def factorial(n):
    while len(_factorial)<=n:
        _factorial.append((_factorial[-1]*len(_factorial))%mod)
    return _factorial[n]

_inv_factorial=[1]
def inv_factorial(n):
    while len(_inv_factorial)<=n:
        _inv_factorial.append((_inv_factorial[-1]*pow(len(_inv_factorial),mod-2,mod))%mod)
    return _inv_factorial[n]

def binom(n,r):
    if r>=mod:
        raise ValueError("r is too big")
    if n<0:
        return 0
    if r>n:
        return 0
    if r<0:
        return 0
    ans=((factorial(n)*inv_factorial(r))%mod*inv_factorial(n-r))%mod
    return ans

def main():
    n,=nin()
    if n==2 or n==3:
        print(-1)
        return
    def up(n):
        new=[]
        if n%2==0:
            for i in range(n+4):
                for j in range(n+4):
                    for di,dj in [(0,1),(1,0)]:
                        if not (0<=i+di<n+4 and 0<=j+dj<n+4):
                            continue
                        if 2<=i+di<n+2 and 2<=j+dj<n+2:
                            continue
                        if (i,i+di)==(0,1):
                            if j not in [0,3]:
                                new.append((i,j,i+di,j+dj))
                        elif (i,i+di)==(n+2,n+3):
                            new.append((i,j,i+di,j+dj))
                        elif (j,j+dj)==(0,1):
                            if i!=n+2:
                                new.append((i,j,i+di,j+dj))
                        elif (j,j+dj)==(n+2,n+3):
                            if i not in [1,n+3]:
                                new.append((i,j,i+di,j+dj))
                        elif i==0 and di==0:
                            if j==2 or (j%2==1 and 3<=j<=n+1):
                                new.append((i,j,i+di,j+dj))
                        elif i==1 and di==0:
                            if j%2==0 and 2<=j<=n:
                                new.append((i,j,i+di,j+dj))
                        elif j in [0,1] and dj==0:
                            if 1<=i<=n+1 and (i+j+1)%2==0:
                                new.append((i,j,i+di,j+dj))
                        elif i in [n+2,n+3] and di==0:
                            if 1<=j<=n+1 and (i+j)%2==0:
                                new.append((i,j,i+di,j+dj))
                        elif j in [n+2,n+3] and dj==0:
                            if 1<=i<=n+1 and (i+j)%2==0:
                                new.append((i,j,i+di,j+dj))
            new.append((1,3,2,3))
        else:
            for i in range(n+4):
                for j in range(n+4):
                    for di,dj in [(0,1),(1,0)]:
                        if not (0<=i+di<n+4 and 0<=j+dj<n+4):
                            continue
                        if 2<=i+di<n+2 and 2<=j+dj<n+2:
                            continue
                        if di==0:
                            if j==0:
                                new.append((i,j,i+di,j+dj))
                            elif j==n+2:
                                if i!=1:
                                    new.append((i,j,i+di,j+dj))
                            elif i in [0,1]:
                                if 2<=j<=n+1 and (i+j)%2==0:
                                    new.append((i,j,i+di,j+dj))
                            elif i in [n+2,n+3]:
                                if 1<=j<=n+1 and (i+j)%2==0:
                                    new.append((i,j,i+di,j+dj))
                        else:
                            if i==0:
                                if j!=0:
                                    new.append((i,j,i+di,j+dj))
                            elif i==n+2:
                                if j not in [1,n+2]:
                                    new.append((i,j,i+di,j+dj))
                            elif j in [0,1]:
                                if (i+j)%2==1:
                                    new.append((i,j,i+di,j+dj))
                            elif j in [n+2,n+3]:
                                if 1<=i<=n+1 and (i+j)%2==0:
                                    new.append((i,j,i+di,j+dj))
            new.append((1,2,2,2))
        return new
    now=[]
    temp=0
    if n%4==0:
        now=[(0, 0, 0, 1), (0, 2, 0, 3), (0, 0, 1, 0), (0, 1, 1, 1), (0, 3, 1, 3), (1, 1, 1, 2), (1, 2, 1, 3), (1, 2, 2, 2), (2, 0, 2, 1), (2, 2, 2, 3), (2, 0, 3, 0), (2, 2, 3, 2), (2, 3, 3, 3), (3, 0, 3, 1), (3, 1, 3, 2)]
        temp=4
    elif n%4==2:
        now=[(0,0,0,1),(1,0,1,1,),(1,0,2,0)]
        temp=2
    elif n%4==1:
        now=[]
        temp=1
    elif n%4==3:
        now=[
            (0,0,0,1),
            (0,1,1,1),
            (1,-1,1,0),
            (1,0,2,0),
            (0,2,1,2),
            (1,2,2,2),
            (2,1,2,2),
            (2,1,3,1)
        ]
        now=[(i,2-j,ii,2-jj) for i,j,ii,jj in now]
        temp=3
    final=[]
    while temp<=n:
        k=(n-temp)//2
        for i,j,ii,jj in now:
            if n%2==1 and (temp//4)%2==0:
                final.append((i+k,n-1-(j+k),ii+k,n-1-(jj+k)))
            else:
                final.append((i+k,j+k,ii+k,jj+k))
        now=up(temp)
        temp+=4
    for i,j,ii,jj in final:
        print(i*n+j+1,ii*n+jj+1)


if __name__=="__main__":
    main()