QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#701938#9537. Chinese Chessucup-team5052#TL 2ms5840kbC++144.8kb2024-11-02 14:58:382024-11-02 14:58:38

Judging History

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

  • [2024-11-02 14:58:38]
  • 评测
  • 测评结果：TL
  • 用时：2ms
  • 内存：5840kb
查看
  • [2024-11-02 14:58:38]
  • 提交

answer

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

const int R = 9, C = 8;
int n, sx[99], sy[99], dis[6][99][10][9], xsq[99], ysq[99], qsz;
const string ANS = "JSCMXB";
unordered_map <string, int> vis;
string ssq[6][99], rs;
int hs[6][99];

vector <pair <int, int> > getNext(int x, int y, int t) {
	vector <pair <int, int> > res;
	if (t == 0) {
		// King
		res.push_back(make_pair(x - 1, y));
		res.push_back(make_pair(x + 1, y));
		res.push_back(make_pair(x, y - 1));
		res.push_back(make_pair(x, y + 1));
	} else if (t == 1) {
		// Mandarin
		res.push_back(make_pair(x - 1, y - 1));
		res.push_back(make_pair(x + 1, y - 1));
		res.push_back(make_pair(x - 1, y + 1));
		res.push_back(make_pair(x + 1, y + 1));
	} else if (t == 2) {
		// Rook
		for (int i = 0;i <= R;i++) {
			if (i != x) res.push_back(make_pair(i, y));
		}
		for (int j = 0;j <= C;j++) {
			if (j != y) res.push_back(make_pair(x, j));
		}
	} else if (t == 3) {
		// Knight
		res.push_back(make_pair(x - 1, y - 2));
		res.push_back(make_pair(x - 2, y - 1));
		res.push_back(make_pair(x - 1, y + 2));
		res.push_back(make_pair(x - 2, y + 1));
		res.push_back(make_pair(x + 1, y - 2));
		res.push_back(make_pair(x + 2, y - 1));
		res.push_back(make_pair(x + 1, y + 2));
		res.push_back(make_pair(x + 2, y + 1));
	} else if (t == 4) {
		// Bishop
		res.push_back(make_pair(x - 2, y - 2));
		res.push_back(make_pair(x + 2, y - 2));
		res.push_back(make_pair(x - 2, y + 2));
		res.push_back(make_pair(x + 2, y + 2));
	} else if (t == 5) {
		// Pawn
		if (x <= 4) res.push_back(make_pair(x + 1, y));
		else {
			res.push_back(make_pair(x, y - 1));
			res.push_back(make_pair(x, y + 1));
			res.push_back(make_pair(x + 1, y));
		}
	}
	return res;
}

inline void Bfs(int tp, int idx) {
	memset(dis[tp][idx], 0x3f, sizeof(dis[tp][idx]));
	queue <pair <int, int> > que;
	dis[tp][idx][sx[idx]][sy[idx]] = 0;
	que.push(make_pair(sx[idx], sy[idx]));
	while (!que.empty()) {
		int cx = que.front().first, cy = que.front().second;
		que.pop();
		auto nxt = getNext(cx, cy, tp);
		for (auto [tx, ty] : nxt) {
			if (tx < 0 || tx > R || ty < 0 || ty > C) continue;
			if (dis[tp][idx][cx][cy] + 1 < dis[tp][idx][tx][ty]) {
				dis[tp][idx][tx][ty] = dis[tp][idx][cx][cy] + 1;
				que.push(make_pair(tx, ty));
			}
		}
	}
//	for (int i = 0;i <= R;i++) {
//		for (int j = 0;j <= C;j++) {
//			cout << dis[tp][idx][i][j] << " ";
//		}
//		cout << endl;
//	}
//	cout << endl;
}

inline void Read() {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> sx[i] >> sy[i];
}

inline bool Dfs(int curx, int cury, int lft, bool fixed) {
	if (curx > R) {
		if(fixed)
		{
			vis.clear();
			for (int i = 0;i < 6;i++) {
				for (int j = 1;j <= n;j++) {
					// cout << (int)ssq[i][j][0] << endl;
					if (vis[ssq[i][j]]) return 0;
				}
				for (int j = 1;j <= n;j++) vis[ssq[i][j]] = 1;
			}
		}
		else
		{
			static bool vis[2000010];
			for(int i=0;i<6;i++)
				for(int j=1;j<=n;j++)
					vis[hs[i][j]]=0;
			for(int i=0;i<6;i++)
			{
				for(int j=1;j<=n;j++)
					if(vis[hs[i][j]]) return 0;
				for(int j=1;j<=n;j++) vis[hs[i][j]]=1;
			}
		}
		return 1;
	}
	if ((R + 1) * (C + 1) - (curx * (C + 1) + cury) < lft) return 0;
	if (Dfs(curx + (cury == C), (cury + 1) % (C + 1), lft, fixed)) return 1;
	if (!lft) return 0;
	if(fixed)
	{
		if(lft == 4 && (curx != 4 || cury != 7)) return 0;
		if(lft == 3 && (curx != 4 || cury != 8)) return 0;
		if(lft == 2 && (curx != 9 || cury != 1)) return 0;
		if(lft == 1 && (curx != 9 || cury != 8)) return 0;
	}
	qsz++;
	xsq[qsz] = curx; ysq[qsz] = cury;
	for (int i = 0;i < 6;i++) {
		for (int j = 1;j <= n;j++) {
			int x = min(63, dis[i][j][curx][cury]);
			ssq[i][j][qsz - 1] = (char)x;
			hs[i][j] = hs[i][j] * 64 + x;
		}
	}
	if (Dfs(curx + (cury == C), (cury + 1) % (C + 1), lft - 1, fixed)) return 1;
	for(int i=0;i<6;i++)
		for(int j=1;j<=n;j++)
			hs[i][j]/=64;
	qsz--;
	return 0;
}

inline void Solve() {
	for (int i = 0;i < 6;i++) {
		for (int j = 1;j <= n;j++) Bfs(i, j);
	}
	for (int cnt = 1;cnt <= 4;cnt++) {
		for (int i = 0;i < 6;i++) {
			for (int j = 1;j <= n;j++) ssq[i][j].resize(cnt);
		}
		if (Dfs(0, 0, cnt, cnt == 4)) {
			cout << qsz << endl;
			string qres = "";
			for (int j = 1;j <= qsz;j++) {
				cout << "? " << xsq[j] << " " << ysq[j] << endl;
				int val;
				cin >> val;
				if (val == -1) val = 63;
				qres.push_back((char)val);
			}
			for (int i = 0;i < 6;i++) {
				for (int j = 1;j <= n;j++) {
					if (ssq[i][j] == qres) {
						cout << "! " << ANS[i] << endl;
						return;
					} 
				}
			}
			while(1);
		}
	}
	while(1);
}

inline void ReadTest() {
	n = 90;
	for (int i = 1;i <= n;i++) {
		sx[i] = (i - 1) / (C + 1);
		sy[i] = (i - 1) % (C + 1);
	}
}

int main() {
//	ReadTest();
	Read();
	Solve();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
9 0
6

output:

1
? 7 6
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

4
2 1
2 3
2 5
2 7
5
6

output:

2
? 4 8
? 9 8
! M

result:

ok number is guessed.

Test #3:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

1
2 4
-1
11

output:

2
? 4 8
? 9 8
! B

result:

ok number is guessed.

Test #4:

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

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

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

input:

1
6 0
6

output:

1
? 4 6
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

2
7 7
1 0
-1
8

output:

2
? 4 8
? 9 8
! S

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

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

output:

2
? 4 8
? 9 8
! M

result:

ok number is guessed.

Test #8:

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

input:

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

output:

2
? 4 4
? 9 8
! B

result:

ok number is guessed.

Test #9:

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

input:

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

output:

2
? 3 3
? 8 7
! J

result:

ok number is guessed.

Test #10:

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

input:

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

output:

2
? 4 7
? 7 7
! S

result:

ok number is guessed.

Test #11:

score: -100
Time Limit Exceeded

input:

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

output:

3
? 4 7

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 10:39:59 | OpenSource Project