QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609097#9412. Stop the Castleorz_zWA 3ms33032kbC++147.1kb2024-10-04 10:38:242024-10-04 10:38:25

Judging History

This is the latest submission verdict.

  • [2024-10-04 10:38:25]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 33032kb
  • [2024-10-04 10:38:24]
  • Submitted

answer

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,fast-math")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {
	cerr << "[" << s << "] = [" << x << "]\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {
	for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;
		else if (s[i] == ')' || s[i] == '}') b--;
		else if (s[i] == ',' && b == 0) {
			cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";
			debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);
			break;
		}
}
#ifdef ONLINE_JUDGE
	#define Debug(...)
#else
	#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
	int x = 0;
	bool t = 0;
	char c = getchar();
	while (c < '0' || c > '9') t |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return t ? -x : x;
}
inline void wi(int x) {
	if (x < 0) {
		putchar('-'), x = -x;
	}
	if (x > 9) wi(x / 10);
	putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
	wi(x), putchar(s);
}
bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;

int n, m;

template<class tp>
struct Flow {
	int Node;
	int s, t, lv[_], cur[_];
	int tot = 1, head[_], to[_ << 1], nxt[_ << 1];
	tp w[_ << 1];
	inline void add(int u, int v, tp dis) {
		to[++tot] = v;
		nxt[tot] = head[u];
		w[tot] = dis;
		head[u] = tot;
	}
	inline void Add(int u, int v, tp dis) {
		add(u, v, dis);
		add(v, u, 0);
	}
	inline bool bfs() {
		F(i, 0, Node) lv[i] = -1;
		lv[s] = 0;
		memcpy(cur, head, sizeof(head));
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int p = q.front();
			q.pop();
			for (int eg = head[p]; eg; eg = nxt[eg]) {
				int v = to[eg];
				tp vol = w[eg];
				if (vol > 0 && lv[v] == -1)
					lv[v] = lv[p] + 1, q.push(v);
			}
		}
		return lv[t] != -1;
	}
	tp dfs(int p, tp flow = 2e9) {
		if (p == t)
			return flow;
		tp rmn = flow;
		for (int eg = cur[p]; eg && rmn; eg = nxt[eg]) {
			cur[p] = eg;
			int v = to[eg];
			tp vol = w[eg];
			if (vol > 0 && lv[v] == lv[p] + 1) {
				tp c = dfs(v, min(vol, rmn));
				rmn -= c;
				w[eg] -= c;
				w[eg ^ 1] += c;
			}
		}
		return flow - rmn;
	}
	inline tp dinic() {
		tp ans = 0;
		while (bfs())
			ans += dfs(s);
		return ans;
	}
	void init() {
		F(i, 0, Node) head[i] = 0;
		tot = 1;
		Node = 0;
	}
};
Flow<int> A;

pii a[_], b[_]; int t, C[_];

int mp[805][805], mp1[805][805], mp2[805][805];

bool Med;
signed main() {
	// Mry;
	int T = ri();
	while(T--) {
		A.init();
		n = ri();
		t = 0;
		F(i, 1, n) {
			a[i].fi = ri(), a[i].se = ri();
			C[++t] = a[i].fi, C[++t] = a[i].se;
		}
		m = ri();
		F(i,1 , m) {
			b[i].fi = ri(), b[i].se = ri();
			C[++t] = b[i].fi, C[++t] = b[i].se;
		}
		sort(C + 1, C + t + 1);
		t = unique(C + 1, C + t + 1) - C - 1;
		F(i, 1, n) {
			a[i].fi = lower_bound(C + 1, C + t + 1, a[i].fi) - C;
			a[i].se = lower_bound(C + 1, C + t + 1, a[i].se) - C;
		}
		F(i, 1, m) {
			b[i].fi = lower_bound(C + 1, C + t + 1, b[i].fi) - C;
			b[i].se = lower_bound(C + 1, C + t + 1, b[i].se) - C;
		}
//		t = 10;
		F(i, 1, t) F(j, 1, t) {
			mp[i][j] = mp1[i][j] = mp2[i][j] = 0;
		}
		F(i, 1, n) {
			mp[a[i].fi][a[i].se] = 1;
		}
		F(i, 1, m) {
			mp[b[i].fi][b[i].se] = 2;
		}
//		Debug("haha");
		bool flg = 0;
		int sum = 0;
		int hangnode = 0, lienode = t + t + t;
		static pii Zb[_];
		F(i, 1, t) {
			F(j, 1, t) if(mp[i][j] == 1) {
				int nw = j + 1;
				while(nw <= t && mp[i][nw] != 1) nw++;//, Debug(nw);
//				Debug(i, j);
				if(j < t && j + 1 == nw) {
					flg = 1;
					break;
				}
//				Debug(i, j, nw);
				if(nw == t + 1) break;
				bool fg = 1;
				F(z, j + 1, nw - 1) {
					fg &= (mp[i][z] == 0);
				}
				if(fg) {
					++hangnode;
					sum++;
//					Debug("hang", i, j + 1, nw - 1);
					F(z, j + 1, nw - 1) if(mp[i][z] == 0) mp1[i][z] = hangnode, Zb[hangnode] = {i, z};
				}
//				Debug(t, nw - 1, "done");
				j = nw - 1;
			}
//			Debug(i);
			if(flg) break;
		}
		if(flg) {
			puts("-1");
			continue;
		}
//		Debug("zj");
		F(j, 1, t) {
			F(i, 1, t) if(mp[i][j] == 1) {
				int nw = i + 1;
				while(nw <= t && mp[nw][j] != 1) nw++;
				if(nw == t + 1) break;
				if(i < t && i + 1 == nw) {
					flg = 1;
					break;
				}
				bool fg = 1;
				F(z, i + 1, nw - 1) fg &= (mp[z][j] == 0);
				if(fg) {
					++lienode;
					sum++;
//					Debug("lie", i + 1, nw - 1, j);
					F(z, i + 1, nw - 1) if(mp[z][j] == 0) mp2[z][j] = lienode, Zb[lienode] = {z, j};
				}
				i = nw - 1;
			}
			if(flg) break;
		}
		if(flg) {
			puts("-1");
			continue;
		}
//		Debug("114514");
		A.s = 0, A.t = lienode + 1;
		A.Node = A.t + 2;
		F(i, 1, hangnode) A.Add(A.s, i, 1);
		F(i, t + t + t + 1, lienode) A.Add(i, A.t, 1);
//		Debug(hangnode, t + t + t, lienode);
		vector<tuple<int, int, int, int, int>> g;
		F(i, 1, t) F(j, 1, t) if(mp1[i][j] && mp2[i][j]) {
//			Debug(i, j);
			g.pb({A.tot + 1, i, j, mp1[i][j], mp2[i][j]});
			A.Add(mp1[i][j], mp2[i][j], 1);
		}
		static int Flg[_];
		F(i, 1, lienode) Flg[i] = 0;
		int w = A.dinic();
//		Debug(sum, w);
		cout<<sum - w << '\n';
		for(auto v : g) {
			int a, b, c, d, e;
			tie(a, b, c, d, e) = v;
			if(A.w[a] == 0) {
				cout << C[b] << ' ' << C[c] << '\n';
				Flg[d] = Flg[e] = 1;
			}
		}
		F(i, 1, hangnode) if(!Flg[i]) {
			cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
		}
		F(i, t + t + t + 1, lienode) if(!Flg[i]) {
			cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
		}
		
	}
	// Try;
	return 0;
}

/*

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

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
*/

詳細信息

Test #1:

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

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: 3ms
memory: 26568kb

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

result:

ok ok 21 cases (21 test cases)

Test #3:

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

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
52 139
91 160
94 35
126 61
132 67
154 138
154 496
185 147
187 467
199 432
224 153
260 275
270 305
277 356
306 374
311 186
334 367
349 61
352 112
393 307
35 308
126 300
187 447
224 430
261 491
274 109
277 270
311 481
390 366
440 191
453 374
65 4
143 25
349 35
70 67
80 139
332 177
277 186
287 272
4...

result:

ok ok 2 cases (2 test cases)

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 26388kb

input:

20
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
8
128947560 120560639
264980960 4742...

output:

-1
7
808969359 818037531
808969359 728848949
808969359 914645536
868407775 354711322
136348710 358274214
794031082 762966373
183418803 871951216
1
994132807 568198964
-1
7
64421616 989073442
305178188 568456333
703111224 216862231
235434591 218130772
337391599 218130772
422330841 703111224
514231778...

result:

wrong answer Participant does not find an answer but the jury finds 8 (test case 1)