QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176149#7179. Fischer's Chess Guessing Gameneko_nyaaAC ✓1275ms3976kbC++231.7kb2023-09-11 11:21:302023-09-11 11:21:30

Judging History

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

  • [2023-09-11 11:21:30]
  • 评测
  • 测评结果:AC
  • 用时:1275ms
  • 内存:3976kb
  • [2023-09-11 11:21:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

vector<string> conf;

void init() {
	string s = "RQKBBNRN";
	sort(s.begin(), s.end());

	do {
		vector<int> kpos, rpos, bpos;
		for (int i = 0; i < 8; i++) {
			if (s[i] == 'K') kpos.push_back(i);
			else if (s[i] == 'R') rpos.push_back(i);
			else if (s[i] == 'B') bpos.push_back(i);
		}

		bool ok = 1;
		if (kpos[0] < rpos[0] || kpos[0] > rpos[1]) ok = 0;
		if (bpos[0] % 2 == bpos[1] % 2) ok = 0;
		if (ok) conf.push_back(s);

	} while (next_permutation(s.begin(), s.end()));
	assert(conf.size() == 960);
}

int dist(string s1, string s2) {
	int ans = 0;
	for (int i = 0; i < 8; i++) {
		if (s1[i] == s2[i]) ans++;
	}
	return ans;
}

void solve() {
	random_shuffle(conf.begin(), conf.end());

	vector<int> avail(960, 1);
	for (int _ = 0; _ < 5; _++) {
		if (accumulate(avail.begin(), avail.end(), 0) == 1) {
			break;
		}

		int cz = 0, cost = 999999;
		for (int i = 0; i < 960; i++) {
			vector<int> hist(9);
			for (int j = 0; j < 960; j++) {
				if (!avail[j]) continue;
				hist[dist(conf[i], conf[j])]++;
			}

			int cs = *max_element(hist.begin(), hist.end());
			if (cs < cost) {
				cost = cs;
				cz = i;
			}
		}

		cout << conf[cz] << endl;
		int x; cin >> x;
		if (x == 8) return;

		for (int i = 0; i < 960; i++) {
			if (!avail[i]) continue;
			if (dist(conf[i], conf[cz]) != x) avail[i] = 0;
		}
	}

	for (int i = 0; i < 960; i++) {
		if (avail[i] == 1) {
			cout << conf[i] << endl;
			int x; cin >> x; 
			return;
		}
	}

	assert(0);
}

signed main() {
	//ios::sync_with_stdio(0); cin.tie(0);
	srand(time(NULL));
	init();

	string s; int ts;
	while (cin >> s) {
		if (s == "END") break;
		cin >> ts;
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 17ms
memory: 3976kb

input:

GAME 1
1
5
2
2
8
END

output:

NRBBNKQR
RKBBNQRN
NQRBNKBR
NRKQBRNB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 1245ms
memory: 3748kb

input:

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

output:

NRBBNKQR
RKBBNQRN
NQRBNKBR
NRKQBRNB
RKRBBQNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
NBRNBQKR
RKRQNBBN
RKRBBNQN
NRBBNKQR
RKBBNQRN
RKNBNRBQ
NRKBBRQN
RBBQKNRN
RKRBBNNQ
NRBBNKQR
BRNNKBQR
NBRKNQBR
RNKRQNBB
NRKNRBBQ
RKRBQNBN
RQKNBBRN
NRKQBBNR
BNRNQKRB
RNKBQRBN
RKRBNQBN
RQKBBNRN
NRQBBKNR
BNRNKQRB
NRKBQRBN
NBRKRQBN
RKR...

result:

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

Test #3:

score: 0
Accepted
time: 1201ms
memory: 3808kb

input:

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

output:

NRBBNKQR
RNBBQKRN
RNKQBBNR
BQNRKRNB
RNBBKNQR
RKQBBNNR
RQKBBNRN
NRNBBKQR
RNNKBQRB
QRNKNBBR
RKNBBQNR
NRBBNKQR
RBBNQKRN
BRKBRNQN
RKNBRNBQ
RKNBBNQR
RQKBBNRN
NRQBBKNR
QRKBNNBR
BRNKQNRB
RKQBNNBR
NRNBBKQR
RQKBBNRN
RBNNBKRQ
QRBBKNRN
NNBBRQKR
RKNBQNBR
NRNBBKQR
RNKBBQRN
QRBBNNKR
BRQKNNRB
QBNRKRBN
RKNBNQBR
RQK...

result:

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

Test #4:

score: 0
Accepted
time: 1275ms
memory: 3736kb

input:

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

output:

NRNBBKQR
RNQBBKRN
RNBBKQNR
BBRNNKRQ
BNNRKBQR
QRKRBBNN
NRBBNKQR
RQBBKNRN
BNQNRBKR
BRKRNBNQ
NRKRBBQN
NRNBBKQR
RQKBBNRN
BRKBNQNR
RBQKNRBN
NRQKBBNR
NRKRBBNQ
NRNBBKQR
RNQBBKRN
BRNQKBRN
RNBNQBKR
NRQKBRNB
QRKRBNNB
NRNBBKQR
RNKBBQRN
NBBRQKRN
BBNNRKQR
NQNRBBKR
NRKRBQNB
RQKBBNRN
NRQBBKNR
BRNBQNKR
NRQBKRBN
BRN...

result:

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

Test #5:

score: 0
Accepted
time: 1271ms
memory: 3688kb

input:

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

output:

NRNBBKQR
RKNBBQRN
RKNBNRBQ
BQNBRKRN
RNKNBQRB
RQNKRBBN
RQKNBBRN
NRKQNBBR
RNBQNBKR
RKNBBQNR
RNQKRBBN
NRNBBKQR
QRKNBBNR
BNRBKRNQ
RKNBRQBN
QRKBRNBN
RNNKRBBQ
NRBBNKQR
RKNNRQBB
RBKNBRNQ
NNBQRBKR
RQNKRNBB
RQKNBBRN
RQBKNNRB
RKBRNBNQ
RNQKNRBB
RNQKRNBB
NRBBNKQR
RKNNRQBB
RNNKBRQB
RNNKRQBB
NRNBBKQR
RKBQNRNB
BNR...

result:

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

Test #6:

score: 0
Accepted
time: 1271ms
memory: 3728kb

input:

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

output:

RQKBBNRN
NRKBBQNR
RBBNKQNR
BRNBKRQN
NBRNBQKR
QRBKNBRN
NRNBBKQR
RNQBBKRN
RKRBBNNQ
RKBNNQRB
RBQKRNBN
NRBKQBRN
RQKBBNRN
RNBBNKRQ
NRQNBKRB
NRBKRQNB
NRBKNBRQ
NRNBBKQR
RKNBBQRN
BRKQNBNR
BRNKNQRB
QRBKNNRB
NRBBNKQR
RQBBKNRN
BRKBQNNR
RKQNRNBB
NNBRQBKR
NRBKQNRB
RQKNBBRN
RQBKNNRB
RBNKBNQR
NRBKNQRB
NRNBBKQR
RNK...

result:

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

Test #7:

score: 0
Accepted
time: 1269ms
memory: 3736kb

input:

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

output:

NRNBBKQR
RKBNQRNB
QNRNKRBB
RBBQKRNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BNRQKRNB
QRBNKRNB
RBBNKRQN
NRBBNKQR
RKBBNQRN
RNKNBRQB
RBNNKRBQ
NBNRQKBR
RBBNKRNQ
NRNBBKQR
RKBNQRNB
RBBKQNRN
NBRKQRBN
RBQNKRBN
NRBBNKQR
RKNNRQBB
RBKQRNBN
QBBNRNKR
RBNQKRBN
NRNBBKQR
QRKNBBNR
BQRNKRNB
NBNRKQBR
RKNRNQBB
RBNNKRBQ
RQKNBBRN
NRN...

result:

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

Test #8:

score: 0
Accepted
time: 1274ms
memory: 3708kb

input:

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

output:

NRBBNKQR
RQBBKNRN
BRKBQNNR
BNRBQKRN
QRNBKNBR
RQKBBNRN
NRKBBQNR
RQBNKBNR
NBRQKNBR
NRQBKNBR
RQKBBNRN
RNBBNKRQ
BBRKRNQN
QRKNRNBB
RBBNKNRQ
NRNBKQBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRQKNNR
RQNKNRBB
QRNNKBBR
NRNBBKQR
RQKBBNRN
RBBNQKNR
RKNNRQBB
NBRKQNBR
NRQNKBBR
NRBBNKQR
RQBBKNRN
BNRNQBKR
RNNQBBKR
RBKRBNQN
NRN...

result:

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

Test #9:

score: 0
Accepted
time: 1242ms
memory: 3732kb

input:

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

output:

NRBBNKQR
RNBBQKRN
RNNKQBBR
NRKNBQRB
RKRBNNBQ
QBBRKNNR
NRNBBKQR
RNQBBKRN
BBRQNNKR
NQBRKBNR
BRKQNBRN
NBBRKQNR
NRNBBKQR
RNKBBQRN
NRBKQRNB
NBQNRKBR
NRBBKRNQ
NBBRKNQR
RQKNBBRN
BBQRNNKR
QRNBKNBR
QBNRKNBR
NRNBBKQR
RNQBBKRN
RNQKNBBR
NBRQKNBR
RNKQBRNB
NBQRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
NBQRKNBR
BQNBRKNR
NBN...

result:

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

Test #10:

score: 0
Accepted
time: 1254ms
memory: 3900kb

input:

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

output:

RQKBBNRN
BBNRQKNR
BRKQRBNN
NRKNQRBB
BBRQNKNR
NRNBBKQR
RNQBBKRN
RNQKNBBR
BBRKQNNR
BBRNQKNR
RQKBBNRN
BBRNNKQR
RQKNBBRN
RQBKNNRB
RNKBNQBR
NQRKNBBR
BQRBNKNR
RQKBBNRN
RNBBNKRQ
RBBNKRNQ
NRBKNBQR
NNBQRKRB
BNRBQKNR
RQKBBNRN
RNBBNKRQ
NRQNBKRB
QBBNRKNR
BNRBNKQR
NRNBBKQR
RNKBBQRN
NQBBRNKR
BNNRKBRQ
NRQNBKRB
QBR...

result:

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

Test #11:

score: 0
Accepted
time: 1274ms
memory: 3904kb

input:

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

output:

RQKBBNRN
RBNKBNQR
RQNKBBRN
RQNBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RNQBBNKR
RQKNBBRN
NRKQBBNR
QNNRBBKR
QBRNBKRN
RNNBBQKR
NRBBNKQR
BRNNKBQR
RNKNQBBR
RBNQKNBR
RQNNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBRKRQNN
RNQNBBKR
NRNBBKQR
RQKBBNRN
RBNQBKRN
RKBQNBNR
RNNQBBKR
RQKBBNRN
NRKBBQNR
RBNQBKNR
BRKRQBNN
RNQ...

result:

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

Extra Test:

score: 0
Extra Test Passed