QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759701#9412. Stop the Castlezq500WA 1ms3648kbC++142.3kb2024-11-18 11:20:572024-11-18 11:20:58

Judging History

This is the latest submission verdict.

  • [2024-11-18 11:20:58]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3648kb
  • [2024-11-18 11:20:57]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
	int n, m;
	unordered_map<int, vector<pair<int, int>>>hang, lie;
	cin>>n;
	for(int i=1, x, y; i<=n; i++)
	{
		cin>>x>>y;
		hang[x].push_back({y, 1});
		lie[y].push_back({x, 1});
	}
	cin>>m;
	for(int i=1, x, y; i<=m; i++)
	{
		cin>>x>>y;
		hang[x].push_back({y, 0});
		lie[y].push_back({x, 0});
	}
	vector<array<int, 3>> boy, girl;
	bool ugly = 0;
	for(auto& [x, vec] : hang)
	{
		sort(vec.begin(), vec.end());
		for(int j = 1; j < vec.size(); ++j)
		{
			auto& [y1, op1] = vec[j - 1];
			auto& [y2, op2] = vec[j];
			if(op1 && op2)
			{
				if(y1 + 1 == y2) ugly = 1;
				boy.push_back({ x, y1, y2 });
			}
		}
	}
	for(auto& [y, vec] : lie)
	{
		sort(vec.begin(), vec.end());
		for(int j = 1; j < vec.size(); ++j)
		{
			auto& [x1, op1] = vec[j - 1];
			auto& [x2, op2] = vec[j];
			if(op1 && op2)
			{
				if(x1 + 1 == x2) ugly = 1;
				girl.push_back({ y, x1, x2 });
			}
		}
	}
	n = boy.size(), m = girl.size();
	vector<vector<int>> E(n);
	for(int u = 0; u < n; ++u)
	{
		auto& [x, y1, y2] = boy[u];
		for(int v = 0; v < m; ++v)
		{
			auto& [y, x1, x2] = girl[v];
			if(x1 < x && x < x2 && y1 < y && y < y2)
			{
				E[u].push_back(v);
			}
		}
	}
	if(ugly)
	{
		printf("-1\n");
		return;
	}
	vector<int> npy(m, -1);
	for(int u = 0; u < n; ++u)
	{
		vector<int> vis(m, 0);
		function<bool(int)> dfs = [&](int u) -> bool
		{
			for(auto& v : E[u])
			{
				if(vis[v]) continue;
				vis[v] = 1;
				if(npy[v] == -1 || dfs(npy[v]))
				{
					npy[v] = u;
					return true;
				}
			}
			return false;
		};
		dfs(u);
	}
	vector<pair<int, int>> res;
	vector<int> happy(n, false);
	for(int v = 0; v < m; ++v)
	{
		if(npy[v] != -1)
		{
			happy[npy[v]] = true;
			res.emplace_back(boy[npy[v]][0], girl[v][0]);
		}
		else
		{
			auto& [y, x1, x2] = girl[v];
			res.emplace_back(x1 + x2 >> 1, y);
		}
	}
	for(int u = 0; u < n; ++u)
	{
		if(!happy[u])
		{
			auto& [x, y1, y2] = boy[u];
			res.emplace_back(x, y1 + y2 >> 1);
		}
	}
	cout<<res.size()<<"\n";
	for(auto& [x, y] : res)
	{
		cout<<x<<" "<<y<<"\n";
	}
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int tn=1;
	cin>>tn;
	while(tn--)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

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

output:

2
4 6
2 3
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
35 38
24 12
37 18
5
21 6
23 26
35 50
16 11
16 31
0
1
29 10
0
1
43 28
5
42 44
1 7
1 26
33 28
44 45
0
5
9 1
26 15
29 33
27 41
44 21
1
32 10
0
0
0
0
6
23 10
29 46
35 34
23 44
12 25
29 27
0
3
32 17
20 30
43 28
0
3
24 39
16 36
25 9
6
8 11
6 10
6 9
7 5
6 5
5 5
-1

result:

wrong answer There are still 4 pairs of castles which can attack each other (test case 19)