QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492265#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓34ms3912kbC++201.6kb2024-07-26 10:56:462024-07-26 10:56:47

Judging History

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

  • [2024-07-26 10:56:47]
  • 评测
  • 测评结果:AC
  • 用时:34ms
  • 内存:3912kb
  • [2024-07-26 10:56:46]
  • 提交

answer

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

int main() {
	string piece = "KQRRBBNN";
	sort(piece.begin(), piece.end());
	vector<string> cand;
	do {
		// the king is placed between the two rooks
		int l = piece.find('R');
		int r = piece.find_last_of('R');
		int k = piece.find('K');
		if (k < l || k > r) {
			continue;
		}
		// the white bishop s are placed on opposite-colored squares
		int b1 = piece.find('B');
		int b2 = piece.find_last_of('B');
		if (b1 % 2 == b2 % 2) {
			continue;
		}
		cand.push_back(piece);
	} while (next_permutation(piece.begin(), piece.end()));


	string str;
	while (cin >> str) {
		if (str == "END") {
			break;
		}
		cin >> *new int;
		auto cur = cand;

		while (1) {
			double best = numeric_limits<double>::max();
			string base;
			if (cur.size() == 960) {
				base = "RBBNNQKR";
			} else {
                // DONE UP HERE
				for (auto x : cur) {
					array<int, 9> freq{};
					for (auto y : cur) {
						int cnt = 0;
						for (int i = 0; i < 8; i++) {
							if (x[i] == y[i]) {
								cnt++;
							}
						}
						freq[cnt]++;
					}
					double sum = 0;
					for (int x : freq) {
						if (x) {
							sum += x * x;
						}
					}
					if (sum < best) {
						best = sum;
						base = x;
					}
				}
			}
			cout << base << endl;
			int num;
			cin >> num;
			if (num == 8) {
				break;
			}
			vector<string> ncur;
			for (auto x : cur) {
				int cnt = 0;
				for (int i = 0; i < 8; i++) {
					if (x[i] == base[i]) {
						cnt++;
					}
				}
				if (cnt == num) {
					ncur.push_back(x);
				}
			}
			cur = move(ncur);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

GAME 1
2
3
1
1
2
8
END

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN

result:

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

Test #2:

score: 0
Accepted
time: 30ms
memory: 3608kb

input:

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

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN
RBBNNQKR
RNQBBKRN
BNQNRKRB
RKNBBRQN
RKRBBNQN
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RKRBBNNQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
NBNRBKRQ
RKRBQNBN
RBBNNQKR
RKBNQBRN
RKBQNRNB
RKRBNQBN
RBBNNQKR
RKNBQNBR
RKNNQRBB
RKBBQNRN
RKRBNNBQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNKRBBNQ
RKN...

result:

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

Test #3:

score: 0
Accepted
time: 31ms
memory: 3608kb

input:

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

output:

RBBNNQKR
RKNBQNBR
RKNNQRBB
RKQBBNNR
RBBNNQKR
RKBNQBRN
NNBQRBKR
RBNKRQBN
RKNBBQNR
RBBNNQKR
RKNBQNBR
RNKBQNBR
RKNBBNQR
RBBNNQKR
RKBNQBRN
NNBQRBKR
RBNKRQBN
RKQBNNBR
RBBNNQKR
RKNBQNBR
RBBNNQKR
BBRNQNKR
RBBKNRQN
RKBNRQNB
RKNBNQBR
RBBNNQKR
RKBNQBRN
RBBQKNRN
RKNNBBQR
RKQNBBNR
RBBNNQKR
RKNBQNBR
RKNRNBBQ
RKN...

result:

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

Test #4:

score: 0
Accepted
time: 34ms
memory: 3868kb

input:

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

output:

RBBNNQKR
BNRBKRQN
NRKQRBBN
BRKQRNNB
QRKRBBNN
RBBNNQKR
BNRBKRQN
NNRQBKRB
BQNRKNRB
NQRKRBBN
NRKRBBQN
RBBNNQKR
BNRBKRQN
QRNKRNBB
NRKRBBNQ
RBBNNQKR
BNRBKRQN
QRNKRNBB
NRKRQNBB
QRKRBNNB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
NRKRBQNB
RBBNNQKR
BNRBKRQN
NRKQRBBN
BRNKRBNQ
NRKRBNQB
RBBNNQKR
RNQBBKRN
BNR...

result:

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

Test #5:

score: 0
Accepted
time: 28ms
memory: 3540kb

input:

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

output:

RBBNNQKR
RNQBBKRN
BRKBNNRQ
RKNQBRNB
NBRKBRQN
RQNKRBBN
RBBNNQKR
RNQBBKRN
BNQNRKRB
NQBBRKRN
RNQKRBBN
RBBNNQKR
RNQBBKRN
BRKBNNRQ
BBQRKRNN
NQNBRKBR
RNNKRBBQ
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
RQNKRNBB
RBBNNQKR
RNQBBKRN
RKNBBRNQ
NQRNBKRB
QRBBKNRN
RNQKRNBB
RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
RNN...

result:

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

Test #6:

score: 0
Accepted
time: 26ms
memory: 3608kb

input:

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

output:

RBBNNQKR
RKNBQNBR
BBRKNRQN
QRBKNRNB
QRBKNBRN
RBBNNQKR
RNQBBKRN
BRKBNNRQ
NRBQKBRN
NRBKQBRN
RBBNNQKR
RKNBQNBR
BBRKNRQN
BRKNNBRQ
BRQNNKRB
NRBKNBRQ
RBBNNQKR
RKNBQNBR
NRBQKBNR
BRNNKQRB
NRKRNQBB
QRBKNNRB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRBKQNRB
RBBNNQKR
RKBNQBRN
NNBQRBKR
QRKNNBBR
NRBKNQRB
RBBNNQKR
BNR...

result:

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

Test #7:

score: 0
Accepted
time: 26ms
memory: 3696kb

input:

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

output:

RBBNNQKR
RKBNQBRN
RKBQNRNB
RBBQKRNN
RBBNNQKR
BBRNQNKR
NQBRNBKR
RBBNKRNQ
RBBNKRQN
RBBNNQKR
BBRNQNKR
NQBRNBKR
RBBNKRNQ
RBBNNQKR
RKBNQBRN
RKBQNRNB
RBKNBRQN
RBQNKRBN
RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
RBKQRNBN
RBNQKRBN
RBBNNQKR
RKBNQBRN
NNBQRBKR
BBRNNKRQ
RBKNBRNQ
RBNNKRBQ
RBBNNQKR
RKNBQNBR
RBQKBNRN
RNB...

result:

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

Test #8:

score: 0
Accepted
time: 31ms
memory: 3912kb

input:

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

output:

RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
BRKBQNNR
QRNBKNBR
RBBNNQKR
RNQBBKRN
BRKBNNRQ
BQRKNBRN
NRQBKNBR
RBBNNQKR
RKNBQNBR
RKNRNBBQ
RKBBQRNN
NRNBKQBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRNBKQNR
QRNNKBBR
RBBNNQKR
RKNBQNBR
RBQKBNRN
NRNQBBKR
BRNKNBQR
NRQNKBBR
RBBNNQKR
RNQBBKRN
BRKNRNQB
BBNRKRNQ
NRNQKBBR
RBBNNQKR
RNQ...

result:

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

Test #9:

score: 0
Accepted
time: 30ms
memory: 3696kb

input:

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

output:

RBBNNQKR
RKBNQBRN
RBNKBNQR
RQKBNNBR
QBBRKNNR
RBBNNQKR
BBRNQNKR
NQBRNBKR
NBBRKQNR
RBBNNQKR
RKBNQBRN
RBNKBNQR
BBNNRKQR
NBBRKNQR
RBBNNQKR
RKNBQNBR
RKNRNBBQ
QBNRKNBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRKBNNQR
NBQRKNBR
RBBNNQKR
RKBNQBRN
NNRBBQKR
BQNBNRKR
NBNRKQBR
RBBNNQKR
RKNBQNBR
NRBQKBNR
BRKQNBNR
QNBRKBNR
RBB...

result:

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

Test #10:

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

input:

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

output:

RBBNNQKR
RKBNQBRN
NNRBBQKR
BBRKNNQR
BBRQNKNR
RBBNNQKR
RKBNQBRN
NNBQRBKR
RBNKRQBN
BBRNQKNR
RBBNNQKR
BBRNQNKR
BBRNKQNR
BBRNNKQR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BQRBNKNR
RBBNNQKR
RNQBBKRN
RKNBBRNQ
QNNBRKBR
BNRBQKNR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BNRBKQNR
BNRBNKQR
RBBNNQKR
RKBNQBRN
RBNKBNQR
RQK...

result:

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

Test #11:

score: 0
Accepted
time: 19ms
memory: 3600kb

input:

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

output:

RBBNNQKR
RKBNQBRN
RBNKBNQR
RBKQBNNR
RQNBBNKR
RBBNNQKR
RKBNQBRN
RBNKBNQR
BBNNRKQR
RNQBBNKR
RBBNNQKR
BBRNQNKR
NQBRNBKR
RBBKNNRQ
RNNBBQKR
RBBNNQKR
BBRNQNKR
RBNNBKQR
NBBNRKQR
RQNNBBKR
RBBNNQKR
BBRNQNKR
RBNNBKQR
NBNRBQKR
RNQNBBKR
RBBNNQKR
RKBNQBRN
NNBQRBKR
BNQNRBKR
RNNQBBKR
RBBNNQKR
RKBNQBRN
NNRBBQKR
BQN...

result:

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

Extra Test:

score: 0
Extra Test Passed