QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617313#9412. Stop the CastlelonelywolfWA 1ms3688kbC++202.8kb2024-10-06 14:52:392024-10-06 14:52:40

Judging History

This is the latest submission verdict.

  • [2024-10-06 14:52:40]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3688kb
  • [2024-10-06 14:52:39]
  • Submitted

answer

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

#define int long long  

void solve() {
	int n;
	cin >> n;

	map<int, vector<pair<int, int>>> xr, yr;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		xr[x].push_back({y, 0});
		yr[y].push_back({x, 0});
	}

	int m;
	cin >> m;

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		xr[x].push_back({y, 1});
		yr[y].push_back({x, 1});
	}

	using Point = pair<int, int>;

	vector<pair<Point, Point>> ls;
	for (auto &[x, v] : xr) {
		sort(v.begin(), v.end());
		for (int i = 1; i < v.size(); i++) {
			if (v[i].second == 0 && v[i - 1].second == 0) {
				int l = v[i - 1].first + 1, r = v[i].first - 1;
				if (l > r) {
					cout << -1 << "\n";
					return;
				}
				ls.push_back({{x, l}, {x, r}});
			}
		}
	}
	for (auto &[y, v] : yr) {
		sort(v.begin(), v.end());
		for (int i = 1; i < v.size(); i++) {
			if (v[i].second == 0 && v[i - 1].second == 0) {
				int l = v[i - 1].first + 1, r = v[i].first - 1;
				if (l > r) {
					cout << -1 << "\n";
					return;
				}
				ls.push_back({{l, y}, {r, y}});
			}
		}
	}
	// for (auto [a, b] : ls) {
	// 	cout << "(" << a.first << ", " << a.second << ") " << "(" << b.first << ", " << b.second << ") \n";
	// }
	auto ins = [&](pair<Point, Point> a, pair<Point, Point> b) {
		int x = a.first.first, y1 = a.first.second, y2 = a.second.second;
		int y = b.first.second, x1 = b.first.first, x2 = b.second.first;
		if (x == a.second.first && y != b.second.second) {
			return false;
		}
		if (y < y1 || y > y2) {
			return false;
		}
		if (x < x1 || x > x2) {
			return false;
		}
		return true;
	};
	vector<vector<int>> g(ls.size(), vector<int>(ls.size()));
	vector<int> f(ls.size());
	int ans = 0;
	for (int i = 0; i < ls.size(); i++) {
		for (int j = i + 1; j < ls.size(); j++) {
			if (ins(ls[i], ls[j])) {
				g[i][j] = g[j][i] = 1;
				ans++;
				f[i]++, f[j]++;
			}
		}
	} 
	vector<Point> a;
	for (int i = 0; i < ls.size(); i++) {
		if (f[i] == 0) {
			ans++;
			a.push_back(ls[i].first);
		}
		if (f[i] == 1) {
			for (int j = i + 1; j < ls.size(); j++) {
				if (g[i][j]) {
					a.push_back({ls[i].first.first, ls[j].first.second});
				}
			}
			continue;
		}
		for (int j = i + 1; j < ls.size(); j++) {
			if (!g[i][j]) {
				continue;
			}
			if (f[j] >= 2) {
				g[i][j] = g[j][i] = 0;
				f[i]--, f[j]--;
				ans--;
			}
			if (f[i] < 2) {
				continue;
			}
		}
		for (int j = i + 1; j < ls.size(); j++) {
			if (g[i][j]) {
				a.push_back({ls[i].first.first, ls[j].first.second});
			}
		}
	}

	cout << ans << "\n";
	for (auto [x, y] : a) {
		cout << x << " " << y << "\n";
	}
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    int t;
    cin >> t;
    while (t--) {
    	solve();
    }

    return 0;
}  
  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

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

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
20 12
34 18
29 38
5
16 10
16 15
12 6
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 13
33 10
44 45
42 44
0
5
27 41
29 26
44 4
8 1
21 15
1
32 9
0
0
0
0
6
12 11
23 10
23 44
29 21
35 34
24 46
0
3
20 30
43 25
31 17
0
-1
3
16 36
25 7
17 39
6
5 5
6 5
7 5
8 9
8 10
8 11

result:

ok ok 21 cases (21 test cases)

Test #3:

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

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

46
35 276
52 139
126 275
154 496
185 67
187 433
187 467
199 160
199 432
224 35
224 61
224 393
260 275
261 468
274 67
277 189
306 374
311 147
311 177
311 356
311 455
334 367
352 61
352 138
390 308
393 112
393 153
393 186
393 305
393 307
440 179
453 251
11 4
38 25
240 35
52 67
57 139
271 186
278 272
4...

result:

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