QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178158#7179. Fischer's Chess Guessing Gameucup-team859AC ✓42ms5756kbC++142.2kb2023-09-13 18:42:572023-09-13 18:42:58

Judging History

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

  • [2023-09-13 18:42:58]
  • 评测
  • 测评结果:AC
  • 用时:42ms
  • 内存:5756kb
  • [2023-09-13 18:42:57]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>
#include <map>
using namespace std;

vector<string> a;

int hamming(const string &a, const string &b) {
	int nr = 0;
	for (int i = 0; i < a.size(); ++i)
		if (a[i] == b[i])
			++nr;
	return nr;
}

map<pair<vector<string>, int>, pair<string, int>> f;
int get_depth(const vector<string> &pos, int depth = 6) {
	//cout << depth << endl;
	if (depth < 0)
		return 1;

	if (pos.size() == 0)
		return 0;

	if (pos.size() == 1) {
		f[{pos, depth}] = {pos[0], 1};
		return 1;
	}

	if (pos.size() == 2) {
		f[{pos, depth}] = {pos[0], 2};
		return 2;
	}

	if (f.count({pos, depth}))
		return f[{pos, depth}].second;

	int best = depth + 1;
	string wh;
	for (auto it : pos) {
		vector<string> cnt[9];
		for (auto it2 : pos)
			cnt[hamming(it, it2)].push_back(it2);

		int mx = 0;
		for (int i = 0; i <= 8 && mx < best; ++i)
			mx = max(mx, 1 + get_depth(cnt[i], depth - 1));

		if (mx < best) {
			best = mx;
			wh = it;
		}
		if (best <= depth)
			break;
	}

	for (int j = 0; j <= depth; ++j)
		f[{pos, j}] = {wh, best};
	return best;
}

void solve() {
	vector<string> pos = a;
	int nr = 6, depth = 6;
	bool first = true;
	while (!pos.empty() && nr--) {
		(void)get_depth(pos, depth);
		string wh = f[{pos, depth}].first; 
		depth -= 1;

		vector<string> bst[9];
		for (auto it : pos)
			bst[hamming(it, wh)].push_back(it);

		//for (int i = 0; i <= 8; ++i)
		//	cout << bst[i].size() << " ";
		//cout << endl;
		int x;
		cout << wh << endl;
		cin >> x;
		if (x == 8)
			break;
		pos = bst[x];
	}
	if (nr == -1)
		exit(0);
}

int main() {
	string s = "RQKBBNRN";
	sort(s.begin(), s.end());
	do {
		int sum = 0, nr = 0, bad = false;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == 'B')
				sum += i & 1;
			else if (s[i] == 'R')
				nr += 1;
			else if (s[i] == 'K' && nr != 1) {
				bad = true;
				break;
			}
		}

		if (sum != 1 || bad)
			continue;

		a.push_back(s);
	} while(next_permutation(s.begin(), s.end()));

	while (1) {
		cin >> s;
		if (s == "END")
			break;

		int x;
		cin >> x;
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 5688kb

input:

GAME 1
0
1
2
2
8
END

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 38ms
memory: 5652kb

input:

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

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKRBBNQN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKRNBBQ
QNRKRNBB
RKRBBNNQ
BBNNQRKR
BNQBRKRN
NBBRKQRN
NQRBBKNR
RNKBNQBR
RKRBQNBN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNQNB
RKRBNQBN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQRNBB
RKRBNNBQ
BBNNQRKR
NNBBRKRQ
QRK...

result:

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

Test #3:

score: 0
Accepted
time: 42ms
memory: 5756kb

input:

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

output:

BBNNQRKR
BNQBRKRN
NBBRKQRN
BQRKRNNB
RKNBRNBQ
RKQBBNNR
BBNNQRKR
BBQRKNRN
NNBBRQKR
NNRKQBBR
RKNBBQNR
BBNNQRKR
BBQRKNRN
BNRKNBQR
RKNBBNQR
BBNNQRKR
BNQBRKRN
NBBRKQRN
BQRKRNNB
RNQKNBBR
RKQBNNBR
BBNNQRKR
BBNQRKRN
BNQRNBKR
BQRNKRNB
RKNBQNBR
BBNNQRKR
BBQRKNRN
NNBBRQKR
NNRKQBBR
NRNBBKQR
RKNBNQBR
BBNNQRKR
BBQ...

result:

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

Test #4:

score: 0
Accepted
time: 39ms
memory: 5720kb

input:

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

output:

BBNNQRKR
NNBBRKRQ
QRKRBBNN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQBNRB
NRKQRBBN
NRKRBBNQ
BBNNQRKR
NNBBRKRQ
QRKRBBNN
QRKRBNNB
BBNNQRKR
NNBBRKRQ
NRKRBBQN
NRKRBQNB
BBNNQRKR
NNBBRKRQ
NRKRBBQN
NRKRBNQB
BBNNQRKR
NNBBRKRQ
QRKRBBNN
QRKRBNNB
QRKRNBBN
BBNNQRKR
BNQBRKRN
BRKRNNQB
NRBKQNRB
RNB...

result:

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

Test #5:

score: 0
Accepted
time: 38ms
memory: 5680kb

input:

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

output:

BBNNQRKR
BNQBRKRN
NBBRKQRN
NQRBBKNR
RKQNBNRB
RQNKRBBN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQBNRB
RNQKRBBN
BBNNQRKR
BNQBRKRN
NBBRKQRN
BQRKRNNB
RKNBRNBQ
RNNKRBBQ
BBNNQRKR
BNQBRKRN
BRKRNNQB
NRKBBRNQ
RQBNKNRB
RQNKRNBB
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQRNBB
QRBKRNNB
RNQKRNBB
BBNNQRKR
BNQBRKRN
NBBRKQRN
NQRBBKNR
QRN...

result:

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

Test #6:

score: 0
Accepted
time: 40ms
memory: 5680kb

input:

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

output:

BBNNQRKR
NNBBRKRQ
NQRKBBRN
NQRKRNBB
QRBKNBRN
BBNNQRKR
BNQBRKRN
NBBRKQRN
NBRKRQBN
NRBKQBRN
BBNNQRKR
NNBBRKRQ
NNBRKQRB
NNRKBBRQ
NRBKNBRQ
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKRNBBQ
QRBKNNRB
BBNNQRKR
BNQBRKRN
BRKRNNQB
NRBKQNRB
BBNNQRKR
NNBBRKRQ
NNRKBQRB
NRBKNQRB
BBNNQRKR
BNQBRKRN
NBBRKQRN
NQRNBKRB
QRNKBBRN
BBN...

result:

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

Test #7:

score: 0
Accepted
time: 40ms
memory: 5684kb

input:

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

output:

BBNNQRKR
BBQRKNRN
BBRKRNNQ
BNQNRKRB
NBBRKQNR
RBBQKRNN
BBNNQRKR
BBNQRKRN
BBQRKNNR
BNRQNBKR
RBBNKRQN
BBNNQRKR
BBNQRKRN
BNQRNBKR
NBRNKRBQ
RBBNKRNQ
BBNNQRKR
BBNQRKRN
BBQRKNNR
BBRKNRNQ
NBRQBNKR
RBQNKRBN
BBNNQRKR
BBNQRKRN
BBNRKNRQ
BBRQKRNN
RBNQKRBN
BBNNQRKR
BBNNRKRQ
BBNRKRNQ
RBNNKRBQ
BBNNQRKR
BNQBRKRN
NBB...

result:

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

Test #8:

score: 0
Accepted
time: 41ms
memory: 5676kb

input:

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

output:

BBNNQRKR
BBQRKNRN
BNNBRKRQ
BRKBNNQR
BRKNNQRB
QRNBKNBR
BBNNQRKR
BNQBRKRN
NBBRKQRN
NQRNBKRB
NRQBKNBR
BBNNQRKR
BBQRKNRN
BNRKNBQR
NRNBKQBR
BBNNQRKR
BBNQRKRN
BNQRNBKR
BNRNKRQB
RBQNKNBR
QRNNKBBR
BBNNQRKR
BBQRKNRN
BNNBRKRQ
NBRKBNQR
NRQNKBBR
BBNNQRKR
BBQRKNRN
BNRKNBQR
RKNBBNQR
NBRQBKNR
NRNQKBBR
BBNNQRKR
BBN...

result:

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

Test #9:

score: 0
Accepted
time: 41ms
memory: 5704kb

input:

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

output:

BBNNQRKR
BBQRKNRN
BBRKNNRQ
BNNRKQRB
BRQBKNNR
QBBRKNNR
BBNNQRKR
BBQRKNRN
BBRKRNNQ
BNQNRKRB
NBBRKQNR
BBNNQRKR
BBQRKNRN
BBRKNNRQ
BNNRKQRB
BRQBKNNR
NBBRKNQR
BBNNQRKR
BBNQRKRN
BBQRKNNR
BQNRKBNR
QBNRKNBR
BBNNQRKR
BBQRKNRN
BQNRKBRN
NBQRKNBR
BBNNQRKR
BBNQRKRN
BBQRKNNR
BBRKNQNR
NBNRKQBR
BBNNQRKR
BNQBRKRN
BRK...

result:

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

Test #10:

score: 0
Accepted
time: 33ms
memory: 5668kb

input:

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

output:

BBNNQRKR
BBNQRKRN
BBNRKNRQ
BBRQNKNR
BBNNQRKR
BBNNRKQR
BBNQRNKR
BBRNQKNR
BBNNQRKR
BBNNRKRQ
BBNRKRNQ
BBRNNKQR
BBNNQRKR
BBQRKNRN
BNRKNBQR
BQRBNKNR
BBNNQRKR
BBNQRKRN
BBQRKNNR
BBRKNRNQ
BNRBQKNR
BBNNQRKR
BBQRKNRN
BNRKNBQR
BNRBNKQR
BBNNQRKR
BBNQRKRN
BBQRKNNR
BBRKNRNQ
BNRBQKNR
QBRNBKNR
BBNNQRKR
BBQRKNRN
BNR...

result:

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

Test #11:

score: 0
Accepted
time: 36ms
memory: 5644kb

input:

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

output:

BBNNQRKR
BBNQRKRN
BNQRNBKR
BNRNKRQB
NRNBBQKR
RQNBBNKR
BBNNQRKR
BBQRKNRN
BNNBRKRQ
BRKBNNQR
RNQBBNKR
BBNNQRKR
BBNQRKRN
BNQRNBKR
BQRNKBNR
RNNBBQKR
BBNNQRKR
BBNNRKRQ
BBQRNNKR
BBRKQRNN
QRNNBBKR
RQNNBBKR
BBNNQRKR
BBNQRKRN
NNBRQBKR
NNQBBRKR
NQBBNRKR
RNQNBBKR
BBNNQRKR
BBNQRKRN
BBQRKNNR
BRNKNRQB
RNNBQKBR
RNN...

result:

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

Extra Test:

score: 0
Extra Test Passed