QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#565995 | #8473. Matrices and Determinants | ucup-team1231# | WA | 9ms | 3992kb | C++20 | 2.7kb | 2024-09-15 22:51:11 | 2024-09-15 22:51:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL A[5][5], L[5][5], R[5][5];
void rswap(int i, int j) {
for(int k = 0; k < n; k++) {
swap(A[i][k], A[j][k]); swap(L[k][i], L[k][j]);
}
for(int k = 0; k < n; k++) {
A[i][k] *= -1; L[k][i] *= -1;
}
}
void cswap(int i, int j) {
for(int k = 0; k < n; k++) {
swap(A[k][i], A[k][j]); swap(R[i][k], R[j][k]);
}
for(int k = 0; k < n; k++) {
A[k][i] *= -1; L[i][k] *= -1;
}
}
void raddmul(int i, int j, LL t) {
for(int k = 0; k < n; k++) {
A[i][k] += A[j][k] * t;
L[k][j] -= L[k][i] * t;
}
}
void caddmul(int i, int j, LL t) {
for(int k = 0; k < n; k++) {
A[k][i] += A[k][j] * t;
R[j][k] -= R[i][k] * t;
}
}
void rreduce(int i, int j) {
if(A[i][i] != 0 && A[j][i] % A[i][i] == 0) {
raddmul(j, i, -A[j][i] / A[i][i]);
return;
}
while(A[j][i] != 0) {
raddmul(i, j, -A[i][i] / A[j][i]);
rswap(i, j);
}
}
void creduce(int i, int j) {
if(A[i][i] != 0 && A[i][j] % A[i][i] == 0) {
caddmul(j, i, -A[i][j] / A[i][i]);
return;
}
while(A[i][j] != 0) {
caddmul(i, j, -A[i][i] / A[i][j]);
cswap(i, j);
}
}
void reduce(int m) {
bool ok;
do {
for(int i = 0; i < m - 1; i++) rreduce(m - 1, i);
for(int i = 0; i < m - 1; i++) creduce(m - 1, i);
ok = true;
for(int i = 0; i < m - 1; i++) if(A[m - 1][i] != 0 || A[i][m - 1] != 0) ok = false;
} while(!ok);
}
int X[5], Y[5];
void solve() {
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) {
scanf("%lld", &A[i][j]);
L[i][j] = R[i][j] = i == j;
}
for(int i = n; i >= 1; i--) reduce(i);
LL prod = 1;
for(int i = 0; i < n; i++) prod *= A[i][i];
if(prod <= 0) {
printf("No\n"); return;
}
LL ss = sqrt(prod + 0.5);
if(ss * ss != prod) {
printf("No\n"); return;
}
for(int i = 0; i < n; i++) {
LL g = __gcd(ss, A[i][i]);
X[i] = g;
Y[i] = A[i][i] / g;
ss /= g;
}
printf("Yes\n");
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
printf("%lld ", L[i][j] * X[j]), assert(L[i][j] * X[j] <= 1e18);
printf("\n");
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
printf("%lld ", R[i][j] * Y[i]), assert(R[i][j] * Y[i] <= 1e18);
printf("\n");
}
}
int main() {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3972kb
input:
3 2 2 0 0 2 2 2 1 1 2 1 1
output:
Yes 2 0 0 1 1 0 0 2 No Yes 1 1
result:
ok OK, Accepted. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 9ms
memory: 3992kb
input:
10000 3 10 0 1 0 0 4 2 10 0 3 2 -2 5 -6 9 0 2 1 10 4 -7 0 7 7 0 0 -10 0 0 0 -10 -10 8 -7 3 9 3 -3 3 3 5 -7 -9 -8 -6 -2 4 9 -8 4 -3 -3 -4 0 0 0 7 0 0 10 -4 7 0 4 3 -10 1 -3 5 5 -3 9 0 -5 -5 -10 3 0 4 -8 3 10 9 0 0 10 0 -5 -1 4 1 -10 4 0 7 0 0 0 -2 7 0 1 -2 7 5 5 -10 -1 0 4 3 1 4 0 -2 3 2 -4 -1 2 -10 ...
output:
No No Yes 630 -105 -63 7 0 2 -5 0 -910 152 90 -10 840 -140 -84 9 0 7 0 0 -5 -25 0 0 26 14 2 0 -52 21 19 1 No No No Yes 0 -1 10 20 10 0 0 0 1 -20 0 -20 40 1 40 -3 1 -4 No No No Yes -9 9 0 18 -19 -3 18 -19 -2 9 0 0 9 1 0 -3 -8 1 No Yes 10 15 0 0 1 3 0 2 5 10 -5 0 3 -2 0 18 4 2...
result:
wrong answer WA, B*C not equal to A 4 -7 0 7 7 0 0 -10 0 0 0 -10 -10 8 -7 3 9 (test case 3)