QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#834845#9537. Chinese ChessBallmer Peak (Ali Safari, AmirMohammad Shahrezaei, Alireza Keshavarz)TL 475ms4492kbC++173.8kb2024-12-28 04:28:222024-12-28 04:28:22

Judging History

This is the latest submission verdict.

  • [2024-12-28 04:28:22]
  • Judged
  • Verdict: TL
  • Time: 475ms
  • Memory: 4492kb
  • [2024-12-28 04:28:22]
  • Submitted

answer

#ifdef safar
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <numeric>
 
#else
 
#include <bits/stdc++.h>
 
#endif


#define rep(i, a, b) for(int i = a; i < (b); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

typedef bitset<540> bt;

const int N = 100 + 10;
const int Sq = 4e4;

string names = "JSCMXB";


int id[N][N];
int dis[6][N][N];

bt val[N][N]; // dis pos

int tot = 90;
int n = 10, m = 9;
int pc = 6;

int bst = 4;

unordered_map<bt, pii> mem;

inline int OK(int x){
	return (x + N) % N;
}
pair<int, int> Solve(bt cur, int dep){
	if(mem.count(cur))
		return mem[cur];

	set<int> st;
	rep(i, 0, 6 * tot) if(cur[i]) st.insert(i % 6);
	if(st.size() <= 1) return {0, -1};
	
	if(dep == bst) return {20, -1};

	int mv = -1;
	int rq = 10;
	rep(q, 0, tot){
		set<int> pd;
		rep(i, 0, 6 * tot) if(cur[i]) pd.insert(OK(dis[i % 6][i / 6][q]));

		int cst = 1;
		for(auto ds : pd) cst = max(cst, 1 + Solve(cur & val[ds][q], dep + 1).F);
	
		if(cst <= rq){
			rq = cst;
			mv = q;
		}
		if(cst >= rq) continue;
	}
	return mem[cur] = {rq, mv};
}




bt cur;

int Main(){
	rep(i, 0, 10) rep(j, 0, 9) id[i][j] = i * 9 + j;
	memset(dis, 31, sizeof dis);
	rep(t, 0, 6){
		rep(i, 0, n){
			rep(j, 0, m){
				vector<pii> dlt;
				if(t == 0) dlt = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
				if(t == 1) dlt = {{1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
				if(t == 2){
					rep(i, 1, 11) dlt.pb({0, i});
					rep(i, 1, 11) dlt.pb({0, -i});
					rep(i, 1, 11) dlt.pb({-i, 0});
					rep(i, 1, 11) dlt.pb({i, 0});
				}

				if(t == 3) dlt = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
				if(t == 4) dlt = {{2, -2}, {-2, 2}, {2, 2}, {-2, -2}};

				if(t == 5 && i <= 4) dlt = {{1, 0}};
				if(t == 5 && i >  4) dlt = {{1, 0}, {0, 1}, {0, -1}};
				
				for(auto [dx, dy] : dlt){
					int nx = dx + i;
					int ny = dy + j;
					if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
					dis[t][id[i][j]][id[nx][ny]] = 1;
				}				
			}
		}

		rep(md, 0, tot)rep(u, 0, tot) rep(v, 0, tot){
			dis[t][u][v] = min(dis[t][u][v], dis[t][u][md] + dis[t][md][v]);
		}
		rep(u, 0, tot) rep(v, 0, tot) if(dis[t][u][v] > tot) dis[t][u][v] = -1;

		rep(u, 0, tot) rep(v, 0, tot) val[OK(dis[t][u][v])][v][u * 6 + t] = 1;	
	}


	vector<pii> sts, tmp;


	// vector<int> Q = {0, 1, tot - 2, tot - 1};

	// map<vector<int>, vector<pii> > mp;
	// for(auto st : sts){
	// 	vector<int> X;
	// 	for(auto q : Q) X.pb(dis[st.F][st.S][q]);
	// 	mp[X].pb(st);
	// }
	// for(auto el : mp){
	// 	set<int> tmp;
	// 	for(auto [p, pos] : el.S) tmp.insert(p);
	// 	// cerr << el.S.size() << ' ' << tmp.size() << '\n';
	// 	if(tmp.size() > 1){
	// 		for(auto [p, pos] : el.S) cerr << p << " at (" << pos/m << " , " << pos % m << ")\n";
	// 		cerr << "# ";
	// 		for(auto x : el.F) cerr << x << ' '; cerr << '\n';
	// 		cerr << '\n';
	// 	}

	// }


	int k;
	cin >> k;
	rep(i, 0, k){
		int pos, x, y;
		cin >> x >> y;
		pos = x * m + y;
		rep(p, 0, 6) cur[pos * 6 + p] = 1;
	}
	auto slv = Solve(cur, 0);
	cout << slv.F << '\n';
	while(true){
		set<int> st;
		rep(i, 0, 6 * tot) if(cur[i]) st.insert(i % 6);
		if(st.size() <= 1){
			cout << "! " << names[*st.begin()] << endl;
			break;
		}

		auto slv = Solve(cur, 0);
		cout << "? " << slv.S / m << ' ' << slv.S % m << endl;
	
		int res;
		cin >> res;
		cur &= val[OK(res)][slv.S];
	}
	return 0;
}


int main(){
	ios::sync_with_stdio(0);
	int tc = 1;
	// cin >> tc;
	while(tc --) Main();
	return 0;
}

詳細信息

Test #1:

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

input:

1
9 0
6

output:

1
? 7 6
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 85ms
memory: 4044kb

input:

4
2 1
2 3
2 5
2 7
14
-1

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #3:

score: 0
Accepted
time: 12ms
memory: 4108kb

input:

1
2 4
-1
7

output:

2
? 9 8
? 9 7
! S

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 9ms
memory: 4232kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 13ms
memory: 3948kb

input:

1
6 0
6

output:

1
? 4 6
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 23ms
memory: 4048kb

input:

2
7 7
1 0
16
-1

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 172ms
memory: 4312kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #8:

score: 0
Accepted
time: 241ms
memory: 4328kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #9:

score: 0
Accepted
time: 380ms
memory: 4216kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 475ms
memory: 4304kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #11:

score: 0
Accepted
time: 318ms
memory: 4200kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #12:

score: 0
Accepted
time: 405ms
memory: 4216kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #13:

score: 0
Accepted
time: 300ms
memory: 4424kb

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #14:

score: 0
Accepted
time: 322ms
memory: 4164kb

input:

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

output:

2
? 9 7
? 4 8
! J

result:

ok number is guessed.

Test #15:

score: 0
Accepted
time: 340ms
memory: 4228kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #16:

score: 0
Accepted
time: 382ms
memory: 4492kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #17:

score: 0
Accepted
time: 318ms
memory: 4244kb

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #18:

score: 0
Accepted
time: 389ms
memory: 4208kb

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #19:

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

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #20:

score: 0
Accepted
time: 405ms
memory: 4208kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #21:

score: 0
Accepted
time: 360ms
memory: 4208kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #22:

score: 0
Accepted
time: 402ms
memory: 4248kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #23:

score: 0
Accepted
time: 298ms
memory: 4160kb

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #24:

score: 0
Accepted
time: 324ms
memory: 4120kb

input:

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

output:

2
? 9 7
? 4 8
! J

result:

ok number is guessed.

Test #25:

score: 0
Accepted
time: 362ms
memory: 4240kb

input:

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

output:

2
? 9 8
? 4 8
! J

result:

ok number is guessed.

Test #26:

score: 0
Accepted
time: 341ms
memory: 4184kb

input:

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

output:

2
? 9 8
? 4 8
! B

result:

ok number is guessed.

Test #27:

score: -100
Time Limit Exceeded

input:

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

output:

3
? 9 8
? 9 7
? 7 2
! M

result: