QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349190 | #8335. Fast Hash Transform | ucup-team197# | WA | 8ms | 104596kb | C++17 | 4.4kb | 2024-03-09 23:58:58 | 2024-03-09 23:58:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAXN = 2e4 + 7 ;
int n , q ;
ull pw[ 64 ] ;
struct elem {
ull r[ 64 ] , c[ 64 ] ;
ull v ;
elem ( ) {
v = 0 ;
for ( int i = 0 ; i < 64 ; ++ i ) {
r[ i ] = c[ i ] = pw[ i ] ;
}
}
};
elem a[ MAXN ] ;
ull qret[ 64 ][ 64 ] ;
ull eval ( elem p1 , ull x ) {
ull ret = 0 ;
for ( int i = 0 ; i < 64 ; ++ i ) {
ull aux = __builtin_popcountll ( p1.r[ i ] & x ) ;
if ( ( aux % 2 ) == 1 ) { ret ^= pw[ i ] ; }
}
return ret ;
}
elem merge ( elem p1 , elem p2 ) {
elem ret = elem ( ) ;
ret.v = p2.v ^ eval ( p2 , p1.v ) ;
for ( int i = 0 ; i < 64 ; ++ i ) {
for ( int j = 0 ; j < 64 ; ++ j ) {
ull aux = __builtin_popcount ( p2.r[ i ] & p1.c[ j ] ) ;
if ( ( aux % 2 ) == 1 ) {
ret.r[ i ] ^= pw[ j ] ;
ret.c[ j ] ^= pw[ i ] ;
}
}
}
return ret ;
}
class Tree {
public :
elem tr[ 4 * MAXN ] ;
void init ( int w , int l , int r ) {
if ( l == r ) {
tr[ w ] = a[ l ] ;
return ;
}
int mid = ( l + r ) / 2 ;
init ( 2 * w , l , mid ) ;
init ( 2 * w + 1 , mid + 1 , r ) ;
tr[ w ] = merge ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
}
void update ( int w , int l , int r , int pos ) {
if ( l == r ) {
tr[ w ] = a[ l ] ;
return ;
}
int mid = ( l + r ) / 2 ;
if ( pos <= mid ) { update ( 2 * w , l , mid , pos ) ; }
else { update ( 2 * w + 1 , mid + 1 , r , pos ) ; }
tr[ w ] = merge ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
}
elem query ( int w , int l , int r , int st , int en ) {
if ( l > r || st > en ) { return elem ( ) ; }
if ( r < st || en < l ) { return elem ( ) ; }
if ( st <= l && r <= en ) { return tr[ w ] ; }
int mid = ( l + r ) / 2 ;
return merge ( query ( 2 * w , l , mid , st , en ) , query ( 2 * w + 1 , mid + 1 , r , st , en ) ) ;
}
};
Tree w ;
void create_elem ( int i ) {
int m ; cin >> m ;
ull mat[ 64 ][ 64 ] , hh = 0 ;
for ( int j = 0 ; j < 64 ; ++ j ) {
for ( int t = 0 ; t < 64 ; ++ t ) {
mat[ j ][ t ] = 0 ;
}
}
a[ i ].v = 0 ;
for ( int j = 0 ; j < m ; ++ j ) {
ull rots , ops , val ;
cin >> rots >> ops >> val ;
for ( int t = 0 ; t < 64 ; ++ t ) {
int pos = ( t + rots ) % 64 ;
if ( ( ops & pw[ t ] ) == 0 ) { // OR
if ( ( val & pw[ t ] ) > 0 ) {
a[ i ].v ^= pw[ t ] ;
}
else {
mat[ pos ][ t ] ^= 1 ;
}
}
else { // AND
if ( ( val & pw[ t ] ) > 0 ) {
mat[ pos ][ t ] ^= 1 ;
}
}
}
}
ull en ; cin >> en ;
a[ i ].v ^= en ;
for ( int j = 0 ; j < 64 ; ++ j ) {
a[ i ].r[ j ] = a[ i ].c[ j ] = 0 ;
}
for ( int j = 0 ; j < 64 ; ++ j ) {
for ( int t = 0 ; t < 64 ; ++ t ) {
if ( mat[ j ][ t ] > 0 ) {
a[ i ].r[ j ] ^= pw[ t ] ;
a[ i ].c[ t ] ^= pw[ j ] ;
}
}
}
}
void solve ( ) {
int foo ;
cin >> n >> q >> foo ;
pw[ 0 ] = 1 ;
for ( int i = 1 ; i < 64 ; ++ i ) {
pw[ i ] = 2 * pw[ i - 1 ] ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
create_elem ( i ) ;
}
w.init ( 1 , 1 , n ) ;
while ( q -- ) {
int type ; cin >> type ;
if ( type == 0 ) {
int l , r ;
ull x ;
cin >> l >> r >> x ;
auto ret = w.query ( 1 , 1 , n , l , r ) ;
ull ans = ret.v ^ eval ( ret , x ) ;
cout << ans << "\n" ;
}
else {
int wh ; cin >> wh ;
create_elem ( wh ) ;
w.update ( 1 , 1 , n , wh ) ;
}
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 104596kb
input:
3 5 1 1 4 0 0 51966 1 60 0 0 0 1 0 0 16 15 0 1 1 771 0 2 2 32368 0 3 3 0 1 2 2 0 0 15 61 1 4095 46681 0 1 3 2023
output:
64206 2023 31 6967
result:
wrong answer 4th words differ - expected: '1112', found: '6967'