結果
問題 |
No.1584 Stones around Circle Pond
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:57:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 657 ms / 2,000 ms |
コード長 | 2,889 bytes |
コンパイル時間 | 231 ms |
コンパイル使用メモリ | 82,820 KB |
実行使用メモリ | 98,608 KB |
最終ジャッジ日時 | 2025-03-26 15:59:20 |
合計ジャッジ時間 | 18,654 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 58 |
ソースコード
import sys from fractions import Fraction def solve(): N, L = map(int, sys.stdin.readline().split()) d = list(map(int, sys.stdin.readline().split())) B = list(map(int, sys.stdin.readline().split())) # Check if all pairs sum to the same value if N == 0: print("Yes") return S = B[0] + B[N] for i in range(1, N): if B[i] + B[i + N] != S: print("No") return # Check if S is divisible by L if S % L != 0: print("No") return T = S // L # Compute D array D = [B[i] - B[i + N] for i in range(N)] # Build matrix A A = [] for j in range(N): row = [] for k in range(N): diff = abs(d[k] - d[j]) a = 2 * diff - L row.append(a) A.append(row) # Augmented matrix: A | D aug = [] for i in range(N): row = [Fraction(A[i][k]) for k in range(N)] row.append(Fraction(D[i])) aug.append(row) # Perform Gaussian elimination n = N rank = 0 for col in range(n): # Find the pivot row pivot = -1 for r in range(rank, n): if aug[r][col] != 0: pivot = r break if pivot == -1: continue # Swap with the rank-th row aug[rank], aug[pivot] = aug[pivot], aug[rank] # Normalize the pivot row pivot_val = aug[rank][col] for c in range(col, n + 1): aug[rank][c] /= pivot_val # Eliminate other rows for r in range(n): if r != rank and aug[r][col] != 0: factor = aug[r][col] for c in range(col, n + 1): aug[r][c] -= factor * aug[rank][c] rank += 1 # Check for inconsistency for r in range(rank, n): if aug[r][-1] != 0: print("No") return # Extract solution solution = [Fraction(0) for _ in range(n)] for r in range(rank): leading_col = -1 for c in range(n): if aug[r][c] != 0: leading_col = c break if leading_col == -1: continue # Solve for leading_col val = aug[r][-1] for c in range(leading_col + 1, n): val -= aug[r][c] * solution[c] solution[leading_col] = val # Check if all solutions are integers for z in solution: if z.denominator != 1: print("No") return z_list = [int(z) for z in solution] sum_abs_z = sum(abs(z) for z in z_list) if sum_abs_z > T: print("No") return sum_z = sum(z_list) if (sum_z % 2) != (T % 2): print("No") return print("Yes") if __name__ == "__main__": solve()