QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625828#9412. Stop the CastleOoWA 1ms3624kbC++204.1kb2024-10-09 21:17:552024-10-09 21:17:59

Judging History

This is the latest submission verdict.

  • [2024-10-09 21:17:59]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3624kb
  • [2024-10-09 21:17:55]
  • Submitted

answer

//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define i128 __int128
#define db long double
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
const int N = 310;
//const int M=;
//const int inf=(int)1e9;
//const ll INF=(ll)1e18;
int T, n, m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

vector<int> g[N];
pair<int, int> a[N];
pair<int, int> L[N], R[N];
int Left, Right;

int match[N];
bool vis[N];
bool dfs(int x) {
	for(auto v : g[x]) {
		if(!vis[v]) {
			vis[v] = 1;
			if(!match[v] || dfs(match[v])) {
				match[v] = x;
				return true;
			}
		}
	}
	return false;
}

void solve() {
	n = read();
	
	Left = Right = 0;
	for(int i = 1; i <= n; i++) g[i].clear();
	memset(match, 0, sizeof(match));
	
	map<int, vector<int>> r0, c0, r1, c1;
	map<pair<int, int>, int> id;
	for(int i = 1; i <= n; i++) {
		int R = read(), C = read();
		a[i] = {R, C};
		id[{R, C}] = i;
		r0[R].pb(C);
		c0[C].pb(R);
	}
	m = read();
	for(int i = 1; i <= m; i++) {
		int R = read(), C = read();
		r1[R].pb(C);
		c1[C].pb(R);
	}
	for(auto &[_, v] : r0) sort(v.begin(), v.end());
	for(auto &[_, v] : c0) sort(v.begin(), v.end());
	for(auto &[_, v] : r1) sort(v.begin(), v.end());
	for(auto &[_, v] : c1) sort(v.begin(), v.end());
	for(auto &[row, v] : r0) {
		if(v.size() <= 1) continue;
		for(int i = 0; i + 1 < v.size(); i++) {
			int l = v[i], r = v[i + 1];
			if(r - l == 1) {
				cout << "-1";
				return;
			}
			auto check = [&]() {
				if(r1.find(row) == r1.end()) return true;
				auto &V = r1[row];
				auto it = upper_bound(V.begin(), V.end(), l);
				if(it == V.end()) return true;
				assert(*it != r);
				return *it > r;
			};
			if(check()) L[++Left] = {id[{row,l}], id[{row, r}]};
		}
	}
	for(auto &[col, v] : c0) {
		if(v.size() <= 1) continue;
		for(int i = 0; i + 1 < v.size(); i++) {
			int l = v[i], r = v[i + 1];
			if(r - l == 1) {
				cout << "-1";
				return;
			}
			auto check = [&]() {
				if(c1.find(col) == c1.end()) return true;
				auto &V = c1[col];
				auto it = upper_bound(V.begin(), V.end(), l);
				if(it == V.end()) return true;
				assert(*it != r);
				return *it > r;
			};
			if(check()) R[++Right] = {id[{l,col}], id[{r, col}]};
		}
	}
//	cout << "left:\n";
//	for(int i = 1; i <= Left; i++) cout << L[i].fi << ' ' << L[i].se << '\n';
//	cout << "right:\n";
//	for(int i = 1; i <= Right; i++) cout << R[i].fi << ' ' << R[i].se << '\n';
//	cout << '\n';
//	cout << "debug:\n";
	for(int i = 1; i <= Left; i++)
		for(int j = 1; j <= Right; j++) {
			auto [a1, a2] = L[i];
			auto [b1, b2] = R[j];
//			assert(a[a1].fi == a[a2].fi);
//			assert(a[b1].se == a[b2].se);
			if(a[a1].se < a[b1].se && a[b1].se < a[a2].se &&
			a[b1].fi < a[a1].fi && a[a1].fi < a[b2].fi) g[i].pb(j);
		}
	int cnt = 0;
	for(int i = 1; i <= Left; i++) {
		memset(vis, 0, sizeof(vis));
		if(dfs(i)) cnt++;
	}
//	cout << Left + Right - cnt << '\n';
	vector<bool> okl(Left + 1), okr(Right + 1);
	vector<pair<int, int>> ans;
	for(int i = 1; i <= Right; i++) {
		if(match[i]) {
			int l = match[i], r = i;
			okl[l] = 1, okr[r] = 1;
			int x = L[l].fi, y = R[r].fi;
//			cout << "match " << x << ' ' << y <<'\n';
			ans.pb({a[x].fi, a[y].se});
		}
	}
	for(int i = 1; i <= Left; i++) {
		if(okl[i]) continue;
		int x = L[i].fi;
		ans.pb({a[x].fi, a[x].se + 1});
	}
	for(int i = 1; i <= Right; i++) {
		if(okr[i]) continue;
		int y = R[i].fi;
		ans.pb({a[y].fi + 1, a[y].se});
	}
	assert(ans.size() == Left + Right - cnt);
	cout << ans.size() << '\n';
	for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
signed main()
{
//	freopen("","r",stdin);
//	freopen("","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout<<fixed<<setprecision();
	int T = read();
	while(T--) solve();
	return 0;
}


詳細信息

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 3600kb

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
23 10
35 34
12 11
23 44
29 21
24 46
0
3
20 30
43 25
31 17
0
-13
16 36
25 7
17 39
6
5 5
8 9
6 4
7 3
3 10
2 11

result:

wrong answer Integer parameter [name=K] equals to -13, violates the range [-1, 256] (test case 19)