QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#566018 | #8473. Matrices and Determinants | ucup-team1231# | AC ✓ | 13ms | 3944kb | C++20 | 2.7kb | 2024-09-15 22:53:52 | 2024-09-15 22:53:53 |
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; R[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: 3888kb
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: 0
Accepted
time: 13ms
memory: 3824kb
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 14 7 0 0 65 35 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 5 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 70 15 0 -47 -10 0 1...
result:
ok OK, Accepted. (10000 test cases)
Test #3:
score: 0
Accepted
time: 13ms
memory: 3860kb
input:
10000 3 0 -3 5 5 0 0 2 1 0 4 2 0 -2 0 -7 4 6 4 -2 8 -3 -10 3 -8 3 -7 4 -7 -4 5 2 5 0 0 4 0 0 0 7 -8 7 0 1 2 4 6 -8 -6 4 0 7 2 -3 0 0 0 -9 0 0 -9 0 7 8 9 2 4 -7 8 -10 -8 6 8 -1 6 8 -10 -7 3 2 7 7 7 3 0 0 -10 0 4 -2 -10 -2 5 3 -4 2 2 7 1 10 10 9 -1 2 9 -1 0 9 4 -7 2 -10 0 -5 1 -3 9 -10 -6 -3 3 8 -10 -...
output:
Yes 0 0 -1 5 -10 0 0 1 2 5 -10 20 2 -5 10 0 3 -5 No No No Yes 2205 -266 -31 -3 7056 -851 -99 -9 630 -76 -9 0 -2205 266 31 2 7 0 0 0 63 9 0 0 -42 -76 1 0 -7 -15 -11 1 No No No Yes 0 -1 9 9 9 0 -9 1 No No No No No Yes -24 -6 -7 -12 -3 -3 -12 -4 -4 0 0 2 0 -6 6 -1 6 -12 No Yes -...
result:
ok OK, Accepted. (10000 test cases)
Test #4:
score: 0
Accepted
time: 13ms
memory: 3892kb
input:
10000 3 10 3 10 0 10 0 9 7 0 4 -2 0 5 1 8 -8 -1 0 2 -9 -1 2 3 8 -5 -4 3 -7 0 7 6 7 -9 1 0 0 4 9 -10 1 -5 9 9 1 10 0 5 -8 -9 -8 -7 -6 -10 2 -10 -3 0 -10 4 5 2 4 2 4 -5 -7 8 -1 8 -5 -8 -9 6 0 6 3 9 0 0 1 0 3 6 3 2 2 8 -3 8 -5 4 6 0 0 6 0 -6 0 -6 0 0 0 10 8 -9 -10 -4 4 -9 -10 4 -1 0 -3 -4 -7 8 -3 -3 7 ...
output:
No No No No Yes -10 -3 -30 -10 10 0 -30 1 No No No No No Yes 6 -7 -3 3 -3 0 -3 1 No Yes -10 -4 -10 -5 -5 0 10 -2 No Yes 3 7 0 1 3 0 0 1 No No No Yes 8 8 0 -1 8 8 -7 -8 No Yes -10 -1 -2 20 0 5 -10 0 -2 -5 0 0 12 -2 0 20 0 1 No No No No No Yes 6 2 0 1 -2 -2 9 6 No No No Y...
result:
ok OK, Accepted. (10000 test cases)
Test #5:
score: 0
Accepted
time: 9ms
memory: 3800kb
input:
10000 3 1 -1 0 0 4 0 1 3 9 3 5 6 6 10 -2 -5 10 -4 -7 3 -6 0 1 7 9 -8 0 0 -6 4 -10 4 9 -4 4 -2 3 -7 0 -8 0 -2 -1 -2 3 -4 4 0 0 0 -4 9 -10 0 7 1 0 0 3 -8 7 10 -5 4 -10 8 7 -1 5 4 7 10 -1 -7 0 1 -1 8 7 -4 3 7 0 0 10 7 -1 1 0 1 3 -5 0 -6 6 0 -1 1 7 1 3 -10 1 0 0 -8 -4 0 0 5 4 -9 4 -6 -5 -2 -10 2 4 4 7 -...
output:
Yes -3 2 -1 0 -2 0 0 0 -1 0 0 3 0 -2 0 -1 -3 -9 No Yes 0 0 1 0 1 -8 18 72 -6 162 -36 0 -41 9 0 -6 0 1 No Yes 60 -14 8 -4 -260 61 -23 7 -60 14 -7 3 60 -14 8 -5 -10 0 10 0 -40 -2 40 0 9 -7 -10 0 8 -7 -10 1 No Yes 7 -14 0 0 -1 -1 0 0 1 -21 -14 0 -11 -7 0 1 0 1 No Yes 0 1 0 -2...
result:
ok OK, Accepted. (10000 test cases)
Test #6:
score: 0
Accepted
time: 13ms
memory: 3808kb
input:
10000 3 6 0 0 -10 4 -7 8 0 6 2 8 -2 5 7 4 1 0 0 10 10 0 -10 -10 -6 -10 1 6 10 0 0 0 4 4 3 3 -3 -6 -8 -9 1 -9 -4 6 -6 9 0 -1 0 4 0 7 0 0 -2 7 -10 -1 -10 7 0 -1 0 2 0 7 4 2 -10 6 -2 5 -1 -7 3 3 8 -9 0 9 -6 5 -8 1 9 4 -5 7 -2 -2 -6 -2 -10 4 -1 -10 5 10 -1 -7 2 10 4 1 0 -3 -7 10 -10 4 -3 0 0 1 0 0 0 -3 ...
output:
Yes -12 3 0 -12 2 -7 12 -2 6 0 6 0 2 24 0 2 -4 1 No Yes -600 12 122 61 600 -11 -110 -50 -300 6 61 30 -100 2 20 10 0 -2 0 0 300 -100 0 -50 -36 -10 1 6 13 20 -2 -2 No Yes -210 7 0 0 0 0 0 -1 0 0 1 -1 -1540 51 -42 7 35 0 -35 0 1050 1 -1050 0 -8 0 10 0 2 -7 10 1 No Yes 3 3 No Yes...
result:
ok OK, Accepted. (10000 test cases)
Test #7:
score: 0
Accepted
time: 13ms
memory: 3944kb
input:
10000 3 7 0 0 10 4 5 8 0 7 1 6 3 0 1 0 7 -3 0 5 -8 7 3 -2 -10 2 9 -3 2 -10 5 5 3 1 0 0 0 -2 0 4 9 -8 4 -2 -2 -4 -7 -1 -8 -4 7 4 10 -2 8 -1 4 -6 2 3 3 4 5 0 -2 0 -10 -6 0 4 10 0 10 -6 1 -2 9 10 -6 -7 -3 9 -5 9 -6 6 4 3 7 3 1 0 0 3 0 0 -10 3 0 0 1 3 -10 4 -1 -7 -10 1 5 2 1 -3 1 -4 5 4 6 -2 6 6 4 0 0 0...
output:
Yes -42 7 0 28 -4 5 42 -6 7 -14 -14 0 -83 -84 0 14 12 1 No No No Yes -4 9 -2 -4 8 -2 0 0 1 0 0 4 1 2 0 4 9 -8 No No No No No Yes -25830 849 -120 10 700 -23 3 -1 2100 -69 10 0 17220 -566 80 -7 -7 0 0 0 -210 -10 0 0 21 -69 1 0 0 21 12 1 No Yes 3 3 No Yes -4 5 -4 4 4 0 4 1 No ...
result:
ok OK, Accepted. (10000 test cases)
Test #8:
score: 0
Accepted
time: 9ms
memory: 3848kb
input:
10000 3 0 2 0 8 -7 -6 -3 -8 0 2 -2 9 1 6 4 -9 0 2 7 -2 0 0 0 -1 0 -8 0 -7 7 9 1 4 -8 -7 -9 2 9 7 -8 -8 2 2 0 10 9 9 -10 7 2 -9 0 -6 -9 3 6 7 9 2 7 -9 0 8 10 1 9 4 9 1 -10 -10 2 1 10 -1 -1 7 -1 -3 5 -7 10 8 3 0 0 10 -9 -4 9 -10 0 -4 4 -1 -3 2 -10 8 -7 4 4 1 -9 7 -1 -2 -1 7 -6 2 -6 9 9 0 3 -2 1 -2 -5 ...
output:
Yes -6 -4 2 0 0 -1 54 37 -17 -6 0 6 5 3 -6 -8 7 6 No Yes 0 23 -61 7 28 214 0 0 0 3 -8 0 0 0 0 1 -2912 2996 0 0 381 -392 0 0 143 -147 1 0 -7 7 9 1 No Yes 9 -3 0 1 -3 -3 -6 -9 No Yes 3 3 No No No No No No No No Yes -448 1534 5 -672 2301 7 -28 96 0 336 14 0 98 4 0 41 28 1 No N...
result:
ok OK, Accepted. (10000 test cases)
Test #9:
score: 0
Accepted
time: 13ms
memory: 3900kb
input:
10000 3 9 -3 0 0 10 0 0 -7 10 4 -2 -5 -8 5 -1 -1 -9 -3 -3 1 -2 0 -10 1 -8 4 3 8 7 5 0 -10 0 0 2 -5 4 9 -5 -4 -8 0 -4 -9 -9 -9 -4 -10 2 4 9 9 -9 4 2 0 -10 -9 0 0 9 0 -9 0 9 0 10 1 0 5 4 5 -9 3 -1 9 -10 9 -6 1 5 -5 4 -9 -2 -9 10 1 4 4 1 10 -10 0 9 -6 -8 -6 -9 2 2 -4 9 -7 -7 3 4 0 -2 5 0 0 -4 -3 -8 10 ...
output:
Yes -30 -267 -9 90 800 30 0 0 -1 240 -180 270 -27 20 -30 0 7 -10 No Yes -20 -151 -19 20 150 20 0 0 1 60 -40 80 -8 5 -10 0 2 -5 No No No Yes 2 2 No No No No No No No No No No No No No Yes 1320 163 8 0 0 0 0 -1 -1320 -163 -9 6 810 100 5 0 -30 0 0 15 240 1 0 -120 60 -20 1 -30 10 -2...
result:
ok OK, Accepted. (10000 test cases)
Test #10:
score: 0
Accepted
time: 13ms
memory: 3908kb
input:
10000 3 8 -4 -6 -6 10 0 0 1 0 3 -6 3 -9 10 8 -1 -3 -8 0 4 0 0 -1 3 -4 8 -6 5 0 0 9 0 6 0 10 2 1 10 3 9 5 2 0 0 -10 -8 0 9 3 8 1 -9 -10 3 4 -9 3 -9 4 -8 -6 1 -4 -10 0 0 10 4 0 0 0 8 10 0 0 4 0 -5 -10 8 10 -6 -2 -1 -10 -7 -2 -10 -7 -6 -10 -10 4 0 0 -9 -2 -1 -3 4 -6 0 0 0 -3 -9 0 0 9 4 10 7 -8 -5 -10 2...
output:
Yes 0 0 1 6 -2 -3 0 1 0 3 0 -3 0 1 0 8 -4 -6 No No No Yes 40 329 2 -180 -1480 -10 160 1316 9 60 -40 0 -7 5 0 -44 -20 1 No Yes 0 0 -1 -2 0 0 2 5 -20 -2 0 0 0 1 0 0 -1 -1 0 0 8 10 0 0 60 30 -5 0 -26 -12 2 2 No Yes 27 -17 -81 -2 0 -55 -212 -6 27 -24 -108 -3 -108 68 324 9 63 -12 ...
result:
ok OK, Accepted. (10000 test cases)