QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143244#7024. Distance Between SweetheartsSorting#AC ✓535ms5672kbC++203.8kb2023-08-20 23:18:312023-08-20 23:18:32

Judging History

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

  • [2023-08-20 23:18:32]
  • 评测
  • 测评结果:AC
  • 用时:535ms
  • 内存:5672kb
  • [2023-08-20 23:18:31]
  • 提交

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 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 = 2007 ;

int test_id ;
pii lim[ 3 ] ;

ull dp[ 3 ][ MAXN ][ 11 ][ 2 ] ;
ull sm[ 3 ][ MAXN ][ 11 ][ 2 ] ;
ull ans ;

void proc ( int id ) {
    for ( int i = 0 ; i < MAXN ; ++ i ) {
        for ( int j = 0 ; j < 11 ; ++ j ) {
            for ( int t = 0 ; t < 2 ; ++ t ) {
                dp[ id ][ i ][ j ][ t ] = sm[ id ][ i ][ j ][ t ] = 0 ;
            }
        }
    }
    for ( int x = 0 ; x <= lim[ id ].fi ; ++ x ) {
        for ( int y = 0 ; y <= lim[ id ].se ; ++ y ) {
            int diff = abs ( x - y ) ;
            for ( int bit = 0 ; bit < 11 ; ++ bit ) {
                int cnt = 0 ;
                if ( ( x & ( 1 << bit ) ) > 0 ) { cnt ^= 1 ; }
                if ( ( y & ( 1 << bit ) ) > 0 ) { cnt ^= 1 ; }
                // if ( ( diff & ( 1 << bit ) ) > 0 ) { cnt ^= 1 ; }
                ++ dp[ id ][ diff ][ bit ][ cnt ] ;
            }
        }
    }
    // printf ( "here %d\n" , id ) ;
    for ( int diff = MAXN - 1 ; diff >= 0 ; -- diff ) {
        for ( int j = diff + 1 ; j < MAXN ; ++ j ) {
            for ( int bit = 0 ; bit < 11 ; ++ bit ) {
                for ( int hh = 0 ; hh < 2 ; ++ hh ) {
                    sm[ id ][ j ][ bit ][ hh ] += dp[ id ][ diff ][ bit ][ hh ] ;
                }
            }
        }
    }
}

void solve ( ) {
    ++ test_id ;
    for ( int i = 0 ; i < 3 ; ++ i ) {
        cin >> lim[ i ].fi ;
    }
    for ( int i = 0 ; i < 3 ; ++ i ) {
        cin >> lim[ i ].se ;
    }
    for ( int i = 0 ; i < 3 ; ++ i ) {
        proc ( i ) ;
    }
    ans = 0 ;
    for ( int mx = 0 ; mx < MAXN - 1 ; ++ mx ) {
        for ( int bit = 0 ; bit < 11 ; ++ bit ) {
            for ( int x = 0 ; x < 2 ; ++ x ) {
                for ( int y = 0 ; y < 2 ; ++ y ) {
                    for ( int z = 0 ; z < 2 ; z ++ ) {
                        for ( int small1 = 0 ; small1 < 2 ; ++ small1 ) {
                            for ( int small2 = 0 ; small2 < 2 ; ++ small2 ) {
                                for ( int small3 = 0 ; small3 < 2 ; ++ small3 ) {
                                    if ( small1 + small2 + small3 == 0 ) { continue ; }
                                    ull coef = 1 ;
                                    if ( small1 == 0 ) { coef = coef * sm[ 0 ][ mx ][ bit ][ x ] ; }
                                    else { coef = coef * dp[ 0 ][ mx ][ bit ][ x ] ; }
                                    
                                    if ( small2 == 0 ) { coef = coef * sm[ 1 ][ mx ][ bit ][ y ] ; }
                                    else { coef = coef * dp[ 1 ][ mx ][ bit ][ y ] ; }

                                    if ( small3 == 0 ) { coef = coef * sm[ 2 ][ mx ][ bit ][ z ] ; }
                                    else { coef = coef * dp[ 2 ][ mx ][ bit ][ z ] ; }

                                    int cnt = 0 ;
                                    cnt = x ^ y ^ z ;
                                    if ( ( mx & ( 1 << bit ) ) > 0 ) { cnt ^= 1 ; }
                                    if ( cnt == 1 ) {
                                        ans = ( ans + ( 1 << bit ) * coef ) ;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << "Case #" << test_id << ": " << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 58ms
memory: 5536kb

input:

3
3 1 2 4 3 3
1 2 1 2 1 3
3 2 5 4 3 5

output:

Case #1: 3880
Case #2: 369
Case #3: 24728

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 269ms
memory: 5520kb

input:

10
474 431 418 416 475 400
492 482 487 488 481 499
499 485 486 498 495 485
2000 50 100 200 2000 2000
1999 50 100 200 1998 1997
1999 100 50 200 1998 1997
1995 100 50 200 2000 2000
2000 100 100 100 2000 2000
2000 66 300 100 1995 2000
90 50 600 2000 1990 1800

output:

Case #1: 1733077153413584909
Case #2: 3455567571304141510
Case #3: 3590382470720836074
Case #4: 7430839420470979674
Case #5: 7405417838059708742
Case #6: 7405417923933950624
Case #7: 7409635628016931244
Case #8: 7360521863394701030
Case #9: 14724638002272683520
Case #10: 18310280976211709616

result:

ok 10 lines

Test #3:

score: 0
Accepted
time: 535ms
memory: 5672kb

input:

10
0 0 0 0 0 0
0 0 0 0 2000 0
0 2000 0 2000 0 0
2000 0 2000 0 0 1000
0 2000 2000 1000 2000 0
2000 0 0 2000 2000 2000
2000 1000 1000 1000 0 1000
1000 2000 1000 1000 0 2000
1000 2000 0 2000 2000 1000
2000 1000 2000 2000 0 2000

output:

Case #1: 0
Case #2: 0
Case #3: 2668667000
Case #4: 3481312864224
Case #5: 7170622352475668
Case #6: 15318219825142720
Case #7: 1532830126493028050
Case #8: 3551576938263084184
Case #9: 7693454823803659554
Case #10: 15471446092771136240

result:

ok 10 lines