QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#565995#8473. Matrices and Determinantsucup-team1231#WA 9ms3992kbC++202.7kb2024-09-15 22:51:112024-09-15 22:51:13

Judging History

你现在查看的是最新测评结果

  • [2024-09-15 22:51:13]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3992kb
  • [2024-09-15 22:51:11]
  • 提交

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)