QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#349190#8335. Fast Hash Transformucup-team197#WA 8ms104596kbC++174.4kb2024-03-09 23:58:582024-03-09 23:58:58

Judging History

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

  • [2024-03-09 23:58:58]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:104596kb
  • [2024-03-09 23:58:58]
  • 提交

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'