QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423407 | #8095. Lati@s | Afterlife | WA | 4ms | 3836kb | C++20 | 2.3kb | 2024-05-27 23:56:32 | 2024-05-27 23:56:33 |
Judging History
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!