QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423407#8095. Lati@sAfterlifeWA 4ms3836kbC++202.3kb2024-05-27 23:56:322024-05-27 23:56:33

Judging History

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

  • [2024-05-27 23:56:33]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3836kb
  • [2024-05-27 23:56:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;


#define ForBit(i,x) for(ull i=0,n=x;(1ull<<i)<=n && i < 64;++i) if(n>>i&1)
ull s[64][64]; 
int vis[64][64];
inline ull f(ull x,ull y);
inline ull g(int x,int y){
	if(!x||!y) return 1ull<<(x|y); 
    if(vis[x][y]) return s[x][y];
    // printf("calcg %d %d\n",x,y);
	ull t=1; int upd=x^y; 
    ForBit(i,upd) t<<=(1ull<<i);
	upd=x&y; 
    ForBit(i,upd) t=f(t,3ull<<((1<<i)-1));
    vis[x][y] = vis[y][x] = 1;
	return s[x][y]=s[y][x]=t;
}
inline ull f(ull x,ull y){
	if(!x||!y) return 0; if(x==1||y==1) return max(x,y);
	ull t=0; ForBit(i,x) ForBit(j,y) t^=g(i,j); return t;
}
ull inv(ull x) {
    // printf("INV %lu\n",x) ;
    ull s = -2;
    ull ans = 1;
    while(s) {
        if(s & 1) ans = f(ans , x);
        x = f(x , x);s >>= 1;
    }
    return ans;
}
ull a[155][155];
int n;
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin >> a[i][j];
    for(int i = 1;i <= n;i++) {
        int ff = -1;
        for(int j = i;j <= n;j++) {
            if(a[j][i]) {ff = j ; break ;}
        }
        if(ff == -1) {
            cout << "Second\n" ; return 0;
        }
        for(int j = i;j <= n;j++) swap(a[ff][j] , a[i][j]);
        // puts("OK") ;
        ull Inv = inv(a[i][i]) ;
        // printf("%lu : inv %lu , mul %lu %lu\n",a[i][i] , Inv , f(Inv , a[i][i]) , f(a[i][i] , Inv)) ;
        for(int j = i + 1;j <= n;j++) {
            ull s = f(Inv , a[j][i]) ;
            ull Mul[64] ;
            for(int k = 0;k < 64;k++) {
                Mul[k] = f((1ull << k) , s) ;
                // ForBit(l , s) Mul[k] ^= g(k , l);
            }
            for(int k = i; k <= n;k++) {
                /// a[j][k] += a[i][k] * (-a[j][i] / a[i][i])
                ull d = 0;
                ForBit(l , a[i][k]) d ^= Mul[l] ;
                // printf("D %lu , %lu\n",d,f(a[i][k] , s)) ;
                a[j][k] ^= d;
            }
            // printf("ok %d\n",j) ;
        }
        // for(int i = 1;i <= n;i++ , printf("\n")) for(int j = 1;j <= n;j++) printf("%lu ",a[i][j]) ;
    }
    ull d = 0;
    for(int i = 1;i <= n;i++) d = d ^ a[i][i] ;
    if(d) cout << "First\n" ;
    else cout << "Second\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

3
0 1 2
1 2 3
1 2 1

output:

First

result:

ok Correct!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2
1 2
2 3

output:

Second

result:

ok Correct!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

1
1

output:

First

result:

ok Correct!

Test #4:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

1
0

output:

Second

result:

ok Correct!

Test #5:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

1
10989383527054532353

output:

First

result:

ok Correct!

Test #6:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

2
1005615900205140029 1751816340545810590
9799519860537995223 8238669462598964242

output:

First

result:

ok Correct!

Test #7:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

2
14541323676997420853 9863599201339623558
7531150024641852914 12902197593218027764

output:

Second

result:

ok Correct!

Test #8:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

5
1 1 1 0 1
0 0 1 1 0
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1

output:

First

result:

ok Correct!

Test #9:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

7
0 1 0 0 1 1 1
0 1 1 1 1 0 1
1 0 0 0 1 1 0
1 0 0 0 0 0 1
1 0 1 0 1 1 0
0 1 0 0 1 0 0
0 1 0 0 1 0 1

output:

First

result:

ok Correct!

Test #10:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

8
1 1 0 0 1 1 0 0
0 1 1 0 0 1 0 0
0 1 1 0 0 1 0 1
0 1 0 0 1 0 0 1
1 0 1 1 1 1 1 1
1 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0

output:

Second

result:

ok Correct!

Test #11:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

30
1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0
0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0
1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0
0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1...

output:

Second

result:

ok Correct!

Test #12:

score: 0
Accepted
time: 4ms
memory: 3756kb

input:

150
0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 ...

output:

Second

result:

ok Correct!

Test #13:

score: -100
Wrong Answer
time: 3ms
memory: 3836kb

input:

150
1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 ...

output:

Second

result:

wrong answer Wrong answer!