結果

問題 No.2719 Equal Inner Products in Permutation
コンテスト
ユーザー ecottea
提出日時 2025-02-03 03:31:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,959 bytes
コンパイル時間 693 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 100,480 KB
最終ジャッジ日時 2025-02-03 03:32:11
合計ジャッジ時間 11,295 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def even_construct(n):
    """
    n が偶数の場合，長さ 3n の「良い順列」を構成して返す．
    ここで，n = 2*m とおく．
    ブロック分割：
      A = P[0 .. n-1]
      B = P[n .. 2*n-1]
      C = P[2*n .. 3*n-1]
    以下の式で各ブロックの値を決定する：
      For i = 0,..., m-1:
         A[2*i]   = 6*m - 2*i      ,   A[2*i+1] = 2*i + 1
         B[2*i]   = 4*m - 2*i      ,   B[2*i+1] = 2*i + 2
         C[2*i]   = 6*m - 2*i - 1  ,   C[2*i+1] = 4*m - 2*i - 1
    """
    m = n // 2
    size = 3 * n
    P = [0] * size
    # ブロック A: indices 0 .. n-1 (計 n = 2*m 項)
    for i in range(m):
        P[2*i]     = 6 * m - 2 * i      # i=0: 6*m, i= m-1: 6*m -2*(m-1)
        P[2*i + 1] = 2 * i + 1
    # ブロック B: indices n .. 2*n-1
    for i in range(m):
        P[n + 2*i]     = 4 * m - 2 * i
        P[n + 2*i + 1] = 2 * i + 2
    # ブロック C: indices 2*n .. 3*n-1
    for i in range(m):
        P[2*n + 2*i]     = 6 * m - 2 * i - 1
        P[2*n + 2*i + 1] = 4 * m - 2 * i - 1
    return P

def odd_construct(n):
    """
    n が奇数かつ n>=3 のときの「良い順列」を構成する．
    n = (N-3) + 3 と見て，
      - 偶数部分：サイズ M = n - 3 （M は偶数）に対して even_construct(M)
      - 3 部分：既知の N=3 の良い順列 S3 = [1,2,8,3,6,9,7,5,4] に
        オフセット offset = 3*M を加えたもの
    それぞれをブロック毎に連結して，全体の順列（長さ 3n）を作る．
    """
    M = n - 3  # M は偶数（n>=3 なので M>=0）
    # 偶数部分（M==0 のときは空リスト）
    if M > 0:
        P_even = even_construct(M)  # 長さ 3*M
    else:
        P_even = []
    # N=3 用の固定良い順列（ブロック毎に 3 項ずつ）
    S3 = [1, 2, 8, 3, 6, 9, 7, 5, 4]
    offset = 3 * M
    S3_offset = [x + offset for x in S3]
    # 偶数部分はブロック分けされている：
    #   A_even = P_even[0:M]
    #   B_even = P_even[M:2*M]
    #   C_even = P_even[2*M:3*M]
    # 同様に S3_offset は，先頭 3 項が A3, 次の 3 項が B3, 最後の 3 項が C3
    A_even = P_even[0:M] if M > 0 else []
    B_even = P_even[M:2*M] if M > 0 else []
    C_even = P_even[2*M:3*M] if M > 0 else []
    A3 = S3_offset[0:3]
    B3 = S3_offset[3:6]
    C3 = S3_offset[6:9]
    A_total = A_even + A3
    B_total = B_even + B3
    C_total = C_even + C3
    # 連結して全体の順列を作る
    return A_total + B_total + C_total

def solve():
    import sys
    input_line = sys.stdin.readline().strip()
    if not input_line:
        return
    N = int(input_line)
    # N=1 のときは解が存在しない
    if N == 1:
        print(-1)
        return
    # N >= 2 のとき
    if N % 2 == 0:
        P = even_construct(N)
    else:
        P = odd_construct(N)
    # 出力（空白区切り）
    print(" ".join(map(str, P)))
    
if __name__ == '__main__':
    solve()
0