結果

問題 No.3094 Stapler
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:00:23
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,058 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 93,812 KB
最終ジャッジ日時 2025-10-23 22:37:30
合計ジャッジ時間 12,724 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    N = int(input())
    matrix = []
    for _ in range(N):
        row = input().split()
        matrix.append(row)
    
    # Find the position of '?'
    i0, j0 = -1, -1
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == '?':
                i0, j0 = i, j
                break
        if i0 != -1:
            break
    
    x_candidates = []
    for k in range(N):
        if k == j0:
            continue
        # Check if the current column k has a non-zero value at (i0, k)
        if matrix[i0][k] == '?':
            continue  # This should not happen as per problem statement
        a_ik = int(matrix[i0][k])
        if a_ik == 0:
            # Check if the sum of other terms is zero
            s = 0
            for i in range(N):
                if i == i0:
                    continue
                a_ij = int(matrix[i][j0])
                a_ik_i = int(matrix[i][k])
                s += a_ij * a_ik_i
            if s != 0:
                pass  # Problem states input is valid, so this won't happen
        else:
            # Compute the sum for other terms
            s = 0
            for i in range(N):
                if i == i0:
                    continue
                a_ij = int(matrix[i][j0])
                a_ik_i = int(matrix[i][k])
                s += a_ij * a_ik_i
            if (-s) % a_ik != 0:
                pass  # Problem states input is valid, so this won't happen
            else:
                x_candidate = (-s) // a_ik
                x_candidates.append(x_candidate)
    
    if x_candidates:
        x = x_candidates[0]
        for candidate in x_candidates[1:]:
            if candidate != x:
                pass  # Problem states input is valid, so this won't happen
        print(x)
        return
    
    # Handle cases with no x_candidates
    if j0 == 0 and N == 1:
        print(1)
        return
    elif j0 == 0:
        # Generate possible x by checking all possible values in a range
        sum_rest = 0
        for i in range(N):
            if i == i0:
                continue
            val = int(matrix[i][j0])
            sum_rest += val ** 2
        # Try x in a reasonable range
        for x in range(-1000, 1001):
            temp_matrix = []
            for row in matrix:
                new_row = []
                for val in row:
                    if val == '?':
                        new_row.append(x)
                    else:
                        new_row.append(int(val))
                temp_matrix.append(new_row)
            valid = True
            for j in range(N):
                for k in range(j + 1, N):
                    s = 0
                    for i in range(N):
                        s += temp_matrix[i][j] * temp_matrix[i][k]
                    if s != 0:
                        valid = False
                        break
                if not valid:
                    break
            if valid:
                print(x)
                return
    else:
        # Compute |G|
        g_order = 0
        for i in range(N):
            val = int(matrix[i][0])
            g_order += val ** 2
        # Compute sum_rest for j0 column
        sum_rest = 0
        for i in range(N):
            if i == i0:
                continue
            val = int(matrix[i][j0])
            sum_rest += val ** 2
        # Generate all divisors of g_order
        def get_divisors(n):
            divisors = set()
            for i in range(1, int(math.isqrt(n)) + 1):
                if n % i == 0:
                    divisors.add(i)
                    divisors.add(n // i)
            return sorted(divisors)
        divisors = get_divisors(g_order)
        possible_x = []
        for d in divisors:
            if d < sum_rest:
                continue
            x_sq = d - sum_rest
            if x_sq < 0:
                continue
            sqrt_x = int(math.isqrt(x_sq))
            if sqrt_x * sqrt_x != x_sq:
                continue
            possible_x.append(sqrt_x)
            possible_x.append(-sqrt_x)
        # Check each possible x
        for x in possible_x:
            temp_matrix = []
            for row in matrix:
                new_row = []
                for val in row:
                    if val == '?':
                        new_row.append(x)
                    else:
                        new_row.append(int(val))
                temp_matrix.append(new_row)
            valid = True
            for j in range(N):
                for k in range(j + 1, N):
                    s = 0
                    for i in range(N):
                        s += temp_matrix[i][j] * temp_matrix[i][k]
                    if s != 0:
                        valid = False
                        break
                if not valid:
                    break
            if valid:
                print(x)
                return
    
    # If no solution found (should not happen as per problem statement)
    print(-1)

if __name__ == "__main__":
    main()
0