QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704756#9537. Chinese Chessucup-team5062#WA 3ms4264kbC++205.1kb2024-11-02 20:55:592024-11-02 20:56:00

Judging History

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

  • [2024-11-02 20:56:00]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：4264kb
查看
  • [2024-11-02 20:55:59]
  • 提交

answer

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Candidates {
	pair<long long, long long> x[6];
};

vector<pair<int, int>> Movements[7];
int Dist[90][90][6];
Candidates Vec[90][30];


// ================================================================================== Initialize
void Initialize() {
	Movements[0].push_back(make_pair(+1, 0));
	Movements[0].push_back(make_pair(-1, 0));
	Movements[0].push_back(make_pair(0, +1));
	Movements[0].push_back(make_pair(0, -1));
	Movements[1].push_back(make_pair(+1, +1));
	Movements[1].push_back(make_pair(-1, +1));
	Movements[1].push_back(make_pair(+1, -1));
	Movements[1].push_back(make_pair(-1, -1));
	for (int i = -9; i <= 9; i++) {
		if (i == 0) continue;
		Movements[2].push_back(make_pair(i, 0));
		Movements[2].push_back(make_pair(0, i));
	}
	Movements[3].push_back(make_pair(+2, -1));
	Movements[3].push_back(make_pair(+2, +1));
	Movements[3].push_back(make_pair(+1, -2));
	Movements[3].push_back(make_pair(+1, +2));
	Movements[3].push_back(make_pair(-2, -1));
	Movements[3].push_back(make_pair(-2, +1));
	Movements[3].push_back(make_pair(-1, -2));
	Movements[3].push_back(make_pair(-1, +2));
	Movements[4].push_back(make_pair(+2, +2));
	Movements[4].push_back(make_pair(+2, -2));
	Movements[4].push_back(make_pair(-2, +2));
	Movements[4].push_back(make_pair(-2, -2));

	Movements[5].push_back(make_pair(1, 0));
	Movements[6].push_back(make_pair(1, 0));
	Movements[6].push_back(make_pair(0, -1));
	Movements[6].push_back(make_pair(0, +1));
}

void get_shortest(int stt, int koma) {
	for (int i = 0; i < 90; i++) Dist[stt][i][koma] = (1 << 30);
	queue<int> Q; Q.push(stt);
	Dist[stt][stt][koma] = 1;
	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		int sx = pos / 9;
		int sy = pos % 9;
		int mv = ((koma == 5 && sx >= 5) ? 6 : koma);

		// Move
		for (int i = 0; i < Movements[mv].size(); i++) {
			int cx = sx + Movements[mv][i].first;
			int cy = sy + Movements[mv][i].second;
			if (cx < 0 || cy < 0 || cx > 9 || cy > 8) continue;
			int val = cx * 9 + cy;
			if (Dist[stt][val][koma] == (1 << 30)) {
				Dist[stt][val][koma] = Dist[stt][pos][koma] + 1;
				Q.push(val);
			}
		}
	}
}

void Prepare() {
	for (int cell = 0; cell < 90; cell++) {
		for (int koma = 0; koma < 6; koma++) {
			for (int i = 0; i < 90; i++) {
				int dst = (Dist[i][cell][koma] == (1 << 30) ? 0 : Dist[i][cell][koma]);
				if (i < 45) Vec[cell][dst].x[koma].first += (1LL << i);
				else Vec[cell][dst].x[koma].second += (1LL << (i - 45));
			}
		}
	}
}


// ================================================================================== Apply
Candidates Apply(Candidates a, int cell, int dst) {
	for (int i = 0; i < 6; i++) {
		a.x[i].first &= Vec[cell][dst].x[i].first;
		a.x[i].second &= Vec[cell][dst].x[i].second;
	}
	return a;
}

pair<bool, int> Solve(int dep, int prv, Candidates a) {
	if (dep == 0) return make_pair(false, -1);

	// Recursion
	for (int cell = prv; cell < 90; cell++) {
		bool flag = true;
		for (int dst = 0; dst <= 18; dst++) {
			Candidates b = Apply(a, cell, dst);
			int cnt = 0;
			if (b.x[0] == make_pair(0LL, 0LL)) cnt++;
			if (b.x[1] == make_pair(0LL, 0LL)) cnt++;
			if (b.x[2] == make_pair(0LL, 0LL)) cnt++;
			if (b.x[3] == make_pair(0LL, 0LL)) cnt++;
			if (b.x[4] == make_pair(0LL, 0LL)) cnt++;
			if (b.x[5] == make_pair(0LL, 0LL)) cnt++;
			if (cnt <= 4 && Solve(dep - 1, cell + 1, b) == make_pair(false, -1)) { flag = false; break; }
		}
		if (flag == true) return make_pair(true, cell);
	}
	return make_pair(false, -1);
}


// ================================================================================== Main Function
int main() {
	// Step 1. Input
	int N; cin >> N;
	vector<int> X(N, 0);
	vector<int> Y(N, 0);
	for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
	Initialize();
	for (int i = 0; i < 90; i++) {
		for (int j = 0; j < 6; j++) get_shortest(i, j);
	}
	Prepare();

	// Step 2. Solve
	Candidates Z;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 6; j++) {
			int cur = X[i] * 9 + Y[i];
			if (cur < 45) Z.x[j].first += (1LL << cur);
			else Z.x[j].second += (1LL << (cur - 45));
		}
	}

	// Step 3. Find Min
	int Minv = 0;
	for (int i = 1; i <= 10; i++) {
		pair<bool, int> ret = Solve(i, 0, Z);
		if (ret.first == true) { Minv = i; break; }
	}
	cout << Minv << endl;

	// Step 3. Interaction
	for (int loops = Minv; loops >= 1; loops--) {
		pair<bool, int> ret = Solve(loops, 0, Z);
		cout << "? " << ret.second / 9 << " " << ret.second % 9 << endl;
		int x; cin >> x;
		x++;
		Z = Apply(Z, ret.second, x);
		vector<int> cand;
		if (Z.x[0] != make_pair(0LL, 0LL)) cand.push_back(0);
		if (Z.x[1] != make_pair(0LL, 0LL)) cand.push_back(1);
		if (Z.x[2] != make_pair(0LL, 0LL)) cand.push_back(2);
		if (Z.x[3] != make_pair(0LL, 0LL)) cand.push_back(3);
		if (Z.x[4] != make_pair(0LL, 0LL)) cand.push_back(4);
		if (Z.x[5] != make_pair(0LL, 0LL)) cand.push_back(5);
		if (cand.size() == 1) {
			char role[7] = "JSCMXB";
			cout << "! " << role[cand[0]] << endl;
			return 0;
		}
	}
	return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3916kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 2ms
memory: 4256kb

input:

4
2 1
2 3
2 5
2 7
5
1

output:

2
? 0 0
? 0 6
! M

result:

ok number is guessed.

Test #3:

score: 0
Accepted
time: 2ms
memory: 4260kb

input:

1
2 4
-1
1

output:

2
? 0 0
? 0 2
! X

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 2ms
memory: 4056kb

input:

2
7 7
1 0
-1
6

output:

2
? 0 0
? 7 2
! S

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 2ms
memory: 4220kb

input:

5
8 6
1 3
0 5
2 4
0 2
6
3

output:

2
? 0 0
? 0 3
! J

result:

ok number is guessed.

Test #8:

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

input:

6
0 7
1 6
2 8
0 5
7 6
8 2
-1
14

output:

2
? 0 0
? 8 1
! B

result:

ok number is guessed.

Test #9:

score: 0
Accepted
time: 2ms
memory: 3864kb

input:

7
6 5
3 0
3 2
4 1
4 0
2 4
5 2
5
7

output:

2
? 0 0
? 0 4
! J

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 2ms
memory: 4264kb

input:

8
3 3
2 5
6 2
7 4
1 4
3 0
2 4
3 4
7
-1

output:

2
? 0 1
? 0 0
! S

result:

ok number is guessed.

Test #11:

score: 0
Accepted
time: 2ms
memory: 3952kb

input:

9
2 7
2 4
2 5
2 2
2 1
2 0
2 6
2 3
2 8
6
8

output:

2
? 2 0
? 0 0
! J

result:

ok number is guessed.

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3964kb

input:

10
4 0
0 0
5 0
7 0
8 0
1 0
6 0
9 0
2 0
3 0

output:

3
? 0 0

result:

wrong answer solution think m=3, while jury think m=2.
English 繁體中文 简体中文

服务器时间: 2024-12-12 23:01:57 | 开源项目