結果

問題 No.3094 Stapler
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:24:24
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,840 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 68,444 KB
最終ジャッジ日時 2025-10-23 22:39:10
合計ジャッジ時間 6,600 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

n = int(input())
matrix = []
r = -1
c = -1
for i in range(n):
    row = input().split()
    for j in range(n):
        if row[j] == '?':
            r = i
            c = j
            row[j] = None
        else:
            row[j] = int(row[j])
    matrix.append(row)

# Check if the column is the identity column (all others are positive integers)
identity_col = True
for i in range(n):
    if i == r:
        continue
    val = matrix[i][c]
    if val is None or val <= 0:
        identity_col = False
        break

if identity_col:
    sum_other_squares = 0
    for i in range(n):
        if i == r:
            continue
        sum_other_squares += (matrix[i][c] ** 2)
    
    if sum_other_squares == 0:
        print(1)
    else:
        def get_divisors(s):
            divisors = set()
            for i in range(1, int(math.isqrt(s)) + 1):
                if s % i == 0:
                    divisors.add(i)
                    divisors.add(s // i)
            return sorted(divisors)
        
        divisors = get_divisors(sum_other_squares)
        valid_x = []
        for x in divisors:
            if x <= 0:
                continue
            group_order = sum_other_squares + x * x
            degrees = []
            for i in range(n):
                if i == r:
                    continue
                degrees.append(matrix[i][c])
            degrees.append(x)
            valid = True
            for d in degrees:
                if d <= 0 or group_order % d != 0:
                    valid = False
                    break
            if not valid:
                continue
            
            sum_squares = []
            for j in range(n):
                if j == c:
                    sum_squares_j = group_order
                else:
                    sum_squares_j = sum(matrix[i][j] ** 2 for i in range(n))
                sum_squares.append(sum_squares_j)
            
            valid_sum = True
            for j in range(n):
                if j == c:
                    continue
                if sum_squares[j] == 0 or group_order % sum_squares[j] != 0:
                    valid_sum = False
                    break
            if not valid_sum:
                continue
            
            C = []
            for j in range(n):
                if j == c:
                    C_j = 1
                else:
                    C_j = group_order // sum_squares[j]
                C.append(C_j)
            
            valid_ortho = True
            for j in range(n):
                for k in range(n):
                    sum_val = 0
                    for i in range(n):
                        a = matrix[i][j] if (j != c or i != r) else x
                        b = matrix[i][k] if (k != c or i != r) else x
                        sum_val += a * b
                    if j == k:
                        expected = group_order // C[j]
                    else:
                        expected = 0
                    if sum_val != expected:
                        valid_ortho = False
                        break
                if not valid_ortho:
                    break
            if valid_ortho:
                valid_x.append(x)
        
        print(valid_x[0])
else:
    x_candidates = set()
    for d in range(n):
        if d == c:
            continue
        s = 0
        for i in range(n):
            if i == r:
                continue
            a = matrix[i][c]
            b = matrix[i][d]
            s += a * b
        a_val = matrix[r][d]
        if a_val == 0:
            if s != 0:
                pass
            continue
        else:
            if s % a_val != 0:
                pass
            else:
                x_candidate = -(s // a_val)
                x_candidates.add(x_candidate)
    print(x_candidates.pop())
0