QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173958#7179. Fischer's Chess Guessing Gameucup-team197#AC ✓18ms4032kbC++173.5kb2023-09-10 03:08:122023-09-10 03:08:12

Judging History

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

  • [2023-09-10 03:08:12]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:4032kb
  • [2023-09-10 03:08:12]
  • 提交

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 n = 8 ;
vector < string > s ;

bool ok ( string a ) {
    int r1 = -1 , r2 = -1 , b1 = -1 , b2 = -1 , k = -1 ;
    int tp = 0 ;
    for ( auto c : a ) {
        if ( c == 'K' ) { k = tp ; }
        else if ( c == 'R' ) {
            if ( r1 == -1 ) { r1 = tp ; }
            else { r2 = tp ; }
        }
        else if ( c == 'B' ) {
            if ( b1 == -1 ) { b1 = tp ; }
            else { b2 = tp ; }
        }
        ++ tp ;
    }
    if ( ( b1 % 2 ) == ( b2 % 2 ) ) { return false ; }
    if ( k < r1 || r2 < k ) { return false ; }
    return true ;
}

void gen ( ) {
    string a = "KQRRBBNN" ;
    sort ( a.begin ( ) , a.end ( ) ) ;
    int tot = 0 ;
    do {
        if ( ok ( a ) == true ) { s.push_back ( a ) ; }
    } while ( next_permutation ( a.begin ( ) , a.end ( ) ) ) ;
}

const int LIM = 5007 ;

int tp = 1 ;
string opt[ LIM ] ;
int sz[ LIM ] ;
int to[ LIM ][ 10 ] ;

void calc ( int w , vector < string > rem , int dep ) {
    sz[ w ] = rem.size ( ) ;
    if ( rem.empty ( ) == true ) {
        return ;
    }
    if ( rem.size ( ) <= 1 ) {
        opt[ w ] = rem[ 0 ] ;
        return ;
    }
    pair < int , string > best = { LIM , "" } ;
    int init_val = 4 ;
    int wtf = init_val ;
    for ( auto sr : rem ) {
        int cnt[ 11 ] ;
        for ( int i = 0 ; i <= 10 ; ++ i ) { cnt[ i ] = 0 ; }
        for ( auto hh : rem ) {
            int cm = 0 ;
            for ( int i = 0 ; i < n ; ++ i ) {
                if ( hh[ i ] == sr[ i ] ) { ++ cm ; }
            }
            ++ cnt[ cm ] ;
        }
        int mx = 0 ;
        for ( int i = 0 ; i <= 10 ; ++ i ) {
            mx = max ( mx , cnt[ i ] ) ;
        }
        if ( w == 1 ) {
            -- wtf ;
            if ( wtf == 0 ) { 
                best = make_pair ( mx , sr ) ;
            }
        }
        else if ( best.fi >= mx ) {
            best = make_pair ( mx , sr ) ;
        }
    }
    opt[ w ] = best.se ;
    vector < string > nxt[ 11 ] ;
    for ( auto hh : rem ) {
        int cm = 0 ;
        for ( int i = 0 ; i < n ; ++ i ) {
            if ( hh[ i ] == opt[ w ][ i ] ) { ++ cm ; }
        }
        nxt[ cm ].push_back ( hh ) ;
    }
    for ( int i = 0 ; i <= 8 ; ++ i ) {
        to[ w ][ i ] = ++ tp ;
        calc ( to[ w ][ i ] , nxt[ i ] , dep + 1 ) ;
    }
}

string ans ;

int calc ( string sr ) {
    int cm = 0 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( sr[ i ] == ans[ i ] ) { ++ cm ; }
    }
    return cm ;
}

void play_game ( ) {
    int wh = 1 ;
    while ( 1 ) {
        cout << opt[ wh ] << "\n" ;
        fflush ( stdout ) ;
        // if ( cnt > 6 ) { cout << "wa " << opt[ wh ] << " " << ans << "\n" ;  }
        int ret ; cin >> ret ;
        if ( ret == 8 ) {
            break ;
        }
        else {
            wh = to[ wh ][ ret ] ;
        }
    }
}

void solve ( ) {
    gen ( ) ;
    tp = 1 ;
    calc ( 1 , s , 0 ) ;
    string foo ;
    int test_id ;
    while ( 1 ) {
        cin >> foo ;
        if ( foo[ 0 ] == 'E' ) { break ; }
        cin >> test_id ;
        play_game ( ) ;
    }
}

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: 100
Accepted
time: 8ms
memory: 3996kb

input:

GAME 1
1
3
4
4
8
END

output:

BBNNRQKR
RKQNBNRB
RKNRBBNQ
RKBRNQNB
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 5 (1 test case)

Test #2:

score: 0
Accepted
time: 15ms
memory: 4024kb

input:

GAME 1
1
3
4
4
8
GAME 2
0
4
4
4
4
8
GAME 3
0
3
0
2
8
GAME 4
0
5
5
8
GAME 5
1
2
4
3
8
GAME 6
0
5
3
5
8
GAME 7
0
3
1
1
8
GAME 8
1
4
3
2
8
GAME 9
1
4
4
2
8
GAME 10
0
2
3
4
2
8
GAME 11
2
2
2
1
8
GAME 12
1
6
4
8
GAME 13
0
5
3
8
GAME 14
1
3
3
1
8
GAME 15
1
3
4
3
1
8
GAME 16
0
4
1
8
GAME 17
1
5
3
3
8
GAME ...

output:

BBNNRQKR
RKQNBNRB
RKNRBBNQ
RKBRNQNB
RKRBBQNN
BBNNRQKR
RKQBNRBN
RNQBBKRN
RKQRBBNN
RQKBBRNN
RKRBBNQN
BBNNRQKR
RKQBNRBN
NRKQNRBB
RNQKBBRN
RKRBBNNQ
BBNNRQKR
RKQBNRBN
RNKBQRBN
RKRBQNBN
BBNNRQKR
RKQNBNRB
RQKBNNBR
RQNKNRBB
RKRBNQBN
BBNNRQKR
RKQBNRBN
RNKBQRBN
RKRQNBBN
RKRBNNBQ
BBNNRQKR
RKQBNRBN
NRKQNRBB
RNB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 13ms
memory: 3964kb

input:

GAME 1
1
5
8
GAME 2
3
2
1
8
GAME 3
2
0
2
8
GAME 4
1
4
1
8
GAME 5
2
0
1
4
4
8
GAME 6
3
1
3
8
GAME 7
2
1
4
2
8
GAME 8
2
2
2
2
8
GAME 9
3
2
2
0
8
GAME 10
2
0
2
3
2
8
GAME 11
2
1
8
GAME 12
3
1
3
5
8
GAME 13
2
3
1
4
8
GAME 14
1
3
3
2
8
GAME 15
1
3
5
3
8
GAME 16
1
2
4
2
8
GAME 17
2
2
2
1
2
8
GAME 18
1
2
5...

output:

BBNNRQKR
RKQNBNRB
RKQBBNNR
BBNNRQKR
NBRQBNKR
BNQRNBKR
RKNBBQNR
BBNNRQKR
BBRQKRNN
RNKNBQRB
RKNBBNQR
BBNNRQKR
RKQNBNRB
RQKNBRNB
RKQBNNBR
BBNNRQKR
BBRQKRNN
RNKNBQRB
RQNKNBBR
RQBBNNKR
RKNBQNBR
BBNNRQKR
NBRQBNKR
BRNKNBQR
RKNBNQBR
BBNNRQKR
BBRQKRNN
RKNQNBBR
RQNKRBBN
RKQNBBNR
BBNNRQKR
BBRQKRNN
RBBKRNNQ
BRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 10ms
memory: 3920kb

input:

GAME 1
0
1
3
2
8
GAME 2
0
1
4
0
8
GAME 3
0
0
5
8
GAME 4
0
0
8
GAME 5
1
2
1
3
8
GAME 6
0
0
6
8
GAME 7
0
3
4
4
8
GAME 8
0
2
3
0
8
GAME 9
0
2
2
1
8
GAME 10
0
2
1
3
8
GAME 11
0
1
4
2
8
GAME 12
1
1
0
1
8
GAME 13
3
0
3
5
8
GAME 14
2
2
2
5
8
GAME 15
2
2
4
3
8
GAME 16
2
4
1
5
8
GAME 17
3
0
3
8
GAME 18
3
0
3...

output:

BBNNRQKR
RKQBNRBN
RNKRBNQB
QNBRNKRB
QRKRBBNN
BBNNRQKR
RKQBNRBN
RNKRBNQB
RNBQKNRB
NRKRBBQN
BBNNRQKR
RKQBNRBN
QRKRBNNB
NRKRBBNQ
BBNNRQKR
RKQBNRBN
QRKRBNNB
BBNNRQKR
RKQNBNRB
RQKBNNBR
BRQKNRNB
NRKRBQNB
BBNNRQKR
RKQBNRBN
QRKRBNNB
NRKRBNQB
BBNNRQKR
RKQBNRBN
NRKQNRBB
RQKRNNBB
QRKRNBBN
BBNNRQKR
RKQBNRBN
RNK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 12ms
memory: 3992kb

input:

GAME 1
2
1
4
8
GAME 2
1
2
2
3
8
GAME 3
2
0
2
2
8
GAME 4
2
0
2
3
8
GAME 5
1
4
2
1
8
GAME 6
3
0
6
8
GAME 7
1
1
2
2
2
8
GAME 8
1
1
1
4
8
GAME 9
1
1
2
3
8
GAME 10
1
3
3
4
3
8
GAME 11
2
3
0
6
8
GAME 12
2
3
1
8
GAME 13
1
2
3
3
8
GAME 14
2
3
0
8
GAME 15
2
2
4
1
8
GAME 16
0
3
3
2
8
GAME 17
0
2
2
4
8
GAME 18...

output:

BBNNRQKR
BBRQKRNN
RKNQNBBR
RQNKRBBN
BBNNRQKR
RKQNBNRB
RQKBNNBR
RNBBKQRN
RNQKRBBN
BBNNRQKR
BBRQKRNN
RNKNBQRB
RKNBBNQR
RNNKRBBQ
BBNNRQKR
BBRQKRNN
RNKNBQRB
RKNBBNQR
RQNKRNBB
BBNNRQKR
RKQNBNRB
RQKNBRNB
RKNQBBRN
RNQKRNBB
BBNNRQKR
NBRQBNKR
RNKNRQBB
RNNKRQBB
BBNNRQKR
RKQNBNRB
QNRKBBNR
RNBBNKQR
RNKQRBBN
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 14ms
memory: 3908kb

input:

GAME 1
0
2
3
1
8
GAME 2
0
1
0
6
8
GAME 3
0
1
0
5
8
GAME 4
0
1
2
3
8
GAME 5
0
0
3
6
8
GAME 6
1
2
1
4
4
8
GAME 7
1
2
0
2
8
GAME 8
0
2
4
3
8
GAME 9
1
2
0
1
8
GAME 10
1
4
2
3
3
8
GAME 11
0
1
3
2
2
8
GAME 12
2
0
4
0
8
GAME 13
2
2
2
4
8
GAME 14
3
1
6
4
8
GAME 15
3
1
8
GAME 16
1
0
4
3
8
GAME 17
1
0
4
1
8
G...

output:

BBNNRQKR
RKQBNRBN
RNKQBBRN
RNBQKRNB
QRBKNBRN
BBNNRQKR
RKQBNRBN
RNKRBNQB
NRBQKBRN
NRBKQBRN
BBNNRQKR
RKQBNRBN
RNKRBNQB
NRBQKBRN
NRBKNBRQ
BBNNRQKR
RKQBNRBN
RNKRBNQB
QNRKBBRN
QRBKNNRB
BBNNRQKR
RKQBNRBN
QRKRBNNB
NRBQKNRB
NRBKQNRB
BBNNRQKR
RKQNBNRB
RQKBNNBR
BRQKNRNB
QRBKRNNB
NRBKNQRB
BBNNRQKR
RKQNBNRB
RQK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 18ms
memory: 4032kb

input:

GAME 1
1
1
1
3
8
GAME 2
2
4
6
8
GAME 3
2
4
5
8
GAME 4
2
4
8
GAME 5
2
5
5
8
GAME 6
3
1
1
2
8
GAME 7
0
4
3
3
8
GAME 8
0
4
4
2
8
GAME 9
0
3
1
5
8
GAME 10
1
3
2
2
8
GAME 11
0
2
3
8
GAME 12
1
3
1
4
3
8
GAME 13
1
1
0
8
GAME 14
0
6
5
8
GAME 15
1
1
1
0
8
GAME 16
2
2
1
1
8
GAME 17
1
4
4
3
8
GAME 18
1
2
2
3
3...

output:

BBNNRQKR
RKQNBNRB
QNRKBBNR
QBBRNKRN
RBBQKRNN
BBNNRQKR
BBRQKRNN
RBQNKRBN
RBBNKRQN
BBNNRQKR
BBRQKRNN
RBQNKRBN
RBBNKRNQ
BBNNRQKR
BBRQKRNN
RBQNKRBN
BBNNRQKR
BBRQKRNN
QBRNKRBN
RBNQKRBN
BBNNRQKR
NBRQBNKR
BRNKNBQR
BNRNKQRB
RBNNKRBQ
BBNNRQKR
RKQBNRBN
RNQBBKRN
RKBQNBRN
RQBBKRNN
BBNNRQKR
RKQBNRBN
RNQBBKRN
RKQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 15ms
memory: 4028kb

input:

GAME 1
2
1
3
1
2
8
GAME 2
1
2
4
1
4
8
GAME 3
3
2
1
4
8
GAME 4
3
1
4
8
GAME 5
2
1
3
3
0
8
GAME 6
2
2
0
4
4
8
GAME 7
2
8
GAME 8
3
2
1
0
5
8
GAME 9
3
2
1
1
8
GAME 10
1
0
2
2
2
8
GAME 11
1
0
1
4
8
GAME 12
1
0
1
2
2
8
GAME 13
2
5
4
8
GAME 14
1
1
3
2
2
8
GAME 15
2
4
3
4
8
GAME 16
2
5
8
GAME 17
1
0
3
1
8
G...

output:

BBNNRQKR
BBRQKRNN
RKNQNBBR
RQKNBBNR
BRNKNBRQ
QRNBKNBR
BBNNRQKR
RKQNBNRB
RQKBNNBR
RQNKNRBB
RNBBKNQR
NRQBKNBR
BBNNRQKR
NBRQBNKR
BNQRNBKR
RKNBBQNR
NRNBKQBR
BBNNRQKR
NBRQBNKR
BRNKNBQR
QRNNKBBR
BBNNRQKR
BBRQKRNN
RKNQNBBR
RQKNBBNR
RKNRBQNB
NRQNKBBR
BBNNRQKR
BBRQKRNN
RBBKRNNQ
QNRNKBBR
QRNNKRBB
NRNQKBBR
BBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 11ms
memory: 4032kb

input:

GAME 1
2
3
4
2
8
GAME 2
3
3
1
4
8
GAME 3
2
2
3
3
1
8
GAME 4
3
3
1
8
GAME 5
2
2
2
2
1
8
GAME 6
4
2
2
3
8
GAME 7
1
0
2
8
GAME 8
1
0
4
0
8
GAME 9
1
0
3
3
4
8
GAME 10
2
1
4
3
5
8
GAME 11
2
1
4
4
5
8
GAME 12
1
1
3
1
8
GAME 13
1
2
2
4
8
GAME 14
2
2
3
1
3
8
GAME 15
2
1
2
4
8
GAME 16
2
2
2
0
2
8
GAME 17
2
3...

output:

BBNNRQKR
BBRQKRNN
BRQBKNNR
BRNQKNRB
QBBRKNNR
BBNNRQKR
NBRQBNKR
RNQNBBKR
QBNRKNBR
NBBRKQNR
BBNNRQKR
BBRQKRNN
RBBKRNNQ
QBRKNNBR
RBKNNRBQ
NBBRKNQR
BBNNRQKR
NBRQBNKR
RNQNBBKR
QBNRKNBR
BBNNRQKR
BBRQKRNN
RBBKRNNQ
BRKBQNNR
RKNQBBNR
NBQRKNBR
BBNNRQKR
RBQNBNKR
BRNQNBKR
NNBBRQKR
NBNRKQBR
BBNNRQKR
RKQNBNRB
NQR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 12ms
memory: 3992kb

input:

GAME 1
3
4
1
4
8
GAME 2
4
3
5
2
8
GAME 3
4
3
4
8
GAME 4
2
3
4
1
8
GAME 5
2
3
4
1
6
8
GAME 6
2
2
0
3
4
8
GAME 7
3
4
2
8
GAME 8
2
4
1
2
8
GAME 9
3
5
4
3
8
GAME 10
3
3
2
5
3
8
GAME 11
2
3
1
1
8
GAME 12
3
4
1
5
8
GAME 13
1
1
6
4
8
GAME 14
1
1
4
3
4
8
GAME 15
1
1
4
1
4
8
GAME 16
1
0
4
4
8
GAME 17
1
0
6
4...

output:

BBNNRQKR
NBRQBNKR
RQNBBNKR
NBRKNQBR
BBRQNKNR
BBNNRQKR
RBQNBNKR
QBBNRKNR
QNBNRBKR
BBRNQKNR
BBNNRQKR
RBQNBNKR
QBBNRKNR
BBRNNKQR
BBNNRQKR
BBRQKRNN
BRQBKNNR
BRNQKNRB
BQRBNKNR
BBNNRQKR
BBRQKRNN
BRQBKNNR
BRNQKNRB
BQRBNKNR
BNRBQKNR
BBNNRQKR
BBRQKRNN
RBBKRNNQ
QNRNKBBR
BNRNQKRB
BNRBNKQR
BBNNRQKR
NBRQBNKR
RQN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 17ms
memory: 4008kb

input:

GAME 1
3
4
8
GAME 2
2
0
3
4
8
GAME 3
4
4
3
8
GAME 4
4
5
4
8
GAME 5
3
3
8
GAME 6
3
4
5
8
GAME 7
3
3
3
2
8
GAME 8
4
3
1
5
8
GAME 9
5
4
3
8
GAME 10
4
4
2
5
8
GAME 11
4
2
8
GAME 12
5
3
5
8
GAME 13
2
0
0
4
8
GAME 14
2
0
0
2
8
GAME 15
3
3
2
2
8
GAME 16
3
2
4
8
GAME 17
2
1
4
1
3
8
GAME 18
3
3
4
2
8
GAME 19...

output:

BBNNRQKR
NBRQBNKR
RQNBBNKR
BBNNRQKR
BBRQKRNN
RNKNBQRB
RNNKBBQR
RNQBBNKR
BBNNRQKR
RBQNBNKR
RBBNKQNR
RNNBBQKR
BBNNRQKR
RBQNBNKR
RBKNBQNR
RQNNBBKR
BBNNRQKR
NBRQBNKR
RNQNBBKR
BBNNRQKR
NBRQBNKR
RQNBBNKR
RNNQBBKR
BBNNRQKR
NBRQBNKR
RNQNBBKR
RBBNKNQR
BRQBNNKR
BBNNRQKR
RBQNBNKR
QBBNRKNR
NRNBBQKR
BRNBQNKR
BBN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed