QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143244 | #7024. Distance Between Sweethearts | Sorting# | AC ✓ | 535ms | 5672kb | C++20 | 3.8kb | 2023-08-20 23:18:31 | 2023-08-20 23:18:32 |
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 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