QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173958 | #7179. Fischer's Chess Guessing Game | ucup-team197# | AC ✓ | 18ms | 4032kb | C++17 | 3.5kb | 2023-09-10 03:08:12 | 2023-09-10 03:08:12 |
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 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