QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609491#9412. Stop the CastleUESTC_xxx#TL 3ms16064kbC++145.5kb2024-10-04 13:14:312024-10-04 13:14:32

Judging History

This is the latest submission verdict.

  • [2024-10-04 13:14:32]
  • Judged
  • Verdict: TL
  • Time: 3ms
  • Memory: 16064kb
  • [2024-10-04 13:14:31]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#define LL long long
using namespace std;
const int inf=1e9;
const int mod=998244353;
//int mod;
const int Base=23,Base2=27;
inline int lowbit(int x){return x&(-x);}
inline int Jia(int x){return x>=mod?x-mod:x;}
inline int Jian(int x){return x>=0?x:x+mod;}
int KSM(int a,int b){
	int Ans=1;
	while(b){
		if(b&1)Ans=1LL*Ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return Ans;
}
inline int read(){
	int k=0,ty=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')ty=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		k=k*10+ch-'0';
		ch=getchar();
	}
	return k*ty;
}
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
const int maxn=5e5+5;
struct d{
	int to,next,flow,p1,p2;
}E[maxn];
struct dd{
	int x,y;
}a[maxn];
int h[maxn],n,S,T,all,cnt,dis[maxn],b[maxn],c[maxn],ans;
vector<int>v1[205],v2[205],id1[205],id2[205];
int vis1[205][205],vis2[205][205],m,cur[maxn];
vector<int>::iterator it1,it2;
void add(int x,int y,int z,int p1,int p2){
	E[++cnt]=(d){y,h[x],z,p1,p2};
	h[x]=cnt;
	E[++cnt]=(d){x,h[y],0,0,0};
	h[y]=cnt;
}
bool BFS(){
	queue<int>q;
	for(int i=1;i<=all;++i)dis[i]=inf;
	dis[S]=0;q.push(S);cur[S]=h[S];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x];i;i=E[i].next){
			int y=E[i].to;
			if(E[i].flow&&dis[y]==inf){
				dis[y]=dis[x]+1;
				cur[y]=h[y];
				q.push(y);
			}
		}
	}
	return dis[T]!=inf;
}
int dfs(int x,int maxflow){
	if(x==T)return maxflow;
	int res=0;
	for(int i=cur[x];i;i=E[i].next){
		int y=E[i].to;
		cur[x]=i;
		if(!E[i].flow||dis[y]!=dis[x]+1)continue;
		int t=dfs(y,min(E[i].flow,maxflow));
		res+=t;
		E[i].flow-=t;E[i^1].flow+=t;
		maxflow-=t;
		if(!maxflow)return res;
	}
	return res;
}
void Solve(){
	n=read();
	b[0]=c[0]=0;
	for(int i=1;i<=n;++i){
		a[i].x=read();a[i].y=read();
		b[++b[0]]=a[i].x;
		c[++c[0]]=a[i].y;
	}
	sort(b+1,b+1+b[0]);sort(c+1,c+1+c[0]);
	b[0]=unique(b+1,b+1+b[0])-b-1;
	c[0]=unique(c+1,c+1+c[0])-c-1;
	for(int i=1;i<=b[0];++i)v1[i].clear(),id1[i].clear();
	for(int i=1;i<=c[0];++i)v2[i].clear(),id2[i].clear();
	for(int i=1;i<=max(c[0],b[0]);++i){
		for(int j=0;j<=n;++j)vis1[i][j]=vis2[i][j]=0;
	}
	for(int i=1;i<=n;++i){
		a[i].x=lower_bound(b+1,b+1+b[0],a[i].x)-b;
		a[i].y=lower_bound(c+1,c+1+c[0],a[i].y)-c;
		v1[a[i].x].push_back(c[a[i].y]);
		v2[a[i].y].push_back(b[a[i].x]);
	}
	for(int i=1;i<=b[0];++i)sort(v1[i].begin(),v1[i].end());
	for(int i=1;i<=c[0];++i)sort(v2[i].begin(),v2[i].end());
	m=read();
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		int k=lower_bound(b+1,b+1+b[0],x)-b;
		if(k<=b[0]&&b[k]==x){
			it1=upper_bound(v1[k].begin(),v1[k].end(),y);
			if(it1!=v1[k].begin()&&it1!=v1[k].end()){
				int z=it1-v1[k].begin();
				--z;
				vis1[k][z]=1;
			}
		}
		k=lower_bound(c+1,c+1+c[0],y)-c;
		if(k<=c[0]&&c[k]==y){
			it1=upper_bound(v2[k].begin(),v2[k].end(),x);
			if(it1!=v2[k].begin()&&it1!=v2[k].end()){
				int z=it1-v2[k].begin();
				--z;
				vis2[k][z]=1;
			}
		}
	}
//	for(int i=1;i<=b[0];++i){
//		cout<<"faf  "<<b[i]<<'\n';
//		for(int j=0;j<v1[i].size();++j)cout<<vis1[i][j]<<' ';cout<<'\n';
//	}
	all=0;S=++all;T=++all;ans=0;
	for(int i=1;i<=n+2;++i)h[i]=0;cnt=1;
	for(int i=1;i<=b[0];++i){
		for(int j=0;j+1<v1[i].size();++j){
			if(v1[i][j]+1==v1[i][j+1]){
//				cout<<b[i]<<'\n';
//				cout<<v1[i][j]<<' '<<v1[i][j+1]<<'\n';
				cout<<-1<<'\n';
				return;
			}
			if(vis1[i][j]){
				id1[i].push_back(0);
				continue;
			}
			++ans;
			id1[i].push_back(++all);
			add(S,all,1,0,0);
		}
	}
//	cout<<"FAF\n";
	for(int i=1;i<=c[0];++i){
		for(int j=0;j+1<v2[i].size();++j){
			if(v2[i][j]+1==v2[i][j+1]){
				cout<<-1<<'\n';
				return;
			}
			if(vis2[i][j]){
				id2[i].push_back(0);
				continue;
			}
			++ans;
			id2[i].push_back(++all);
			add(all,T,1,0,0);
		}
	}
	for(int i=1;i<=b[0];++i){
		for(int j=0;j+1<v1[i].size();++j){
			int D=v1[i][j]+1,U=v1[i][j+1]-1;
			int kl=lower_bound(c+1,c+1+c[0],D)-c;
			int kr=upper_bound(c+1,c+1+c[0],U)-c-1;
			for(int k=kl;k<=kr;++k){
				it1=lower_bound(v2[k].begin(),v2[k].end(),b[i]);
				if(it1==v2[k].begin()||it1==v2[k].end())continue;
				int t=it1-v2[k].begin();
				--t;
				if(!id1[i][j]||!id2[k][t])continue;
				add(id1[i][j],id2[k][t],1,b[i],c[k]);
			}
		}
	}
//	cout<<"Ans::"<<ans<<'\n';
	while(BFS())ans-=dfs(S,inf);
	cout<<ans<<'\n';
	for(int i=2;i<=cnt;i+=2){
		if(E[i].flow==0&&E[i].p1!=0){
			cout<<E[i].p1<<' '<<E[i].p2<<'\n';
			int x=E[i].p1,y=E[i].p2;
			int k=lower_bound(b+1,b+1+b[0],x)-b;
			if(k<=b[0]&&b[k]==x){
				it1=upper_bound(v1[k].begin(),v1[k].end(),y);
				if(it1!=v1[k].begin()&&it1!=v1[k].end()){
					int z=it1-v1[k].begin();
					--z;
					vis1[k][z]=1;
				}
			}
			k=lower_bound(c+1,c+1+c[0],y)-c;
			if(k<=c[0]&&c[k]==y){
				it1=upper_bound(v2[k].begin(),v2[k].end(),x);
				if(it1!=v2[k].begin()&&it1!=v2[k].end()){
					int z=it1-v2[k].begin();
					--z;
					vis2[k][z]=1;
				}
			}
		}
	}
//	return;
	for(int i=1;i<=b[0];++i){
		for(int j=0;j+1<v1[i].size();++j){
			if(vis1[i][j]==0)cout<<b[i]<<' '<<v1[i][j]+1<<'\n';
		}
	}
	for(int i=1;i<=c[0];++i){
		for(int j=0;j+1<v2[i].size();++j){
			if(vis2[i][j]==0)cout<<v2[i][j]+1<<' '<<c[i]<<'\n';
		}
	}
}
int main(){
//	freopen("data.txt","r",stdin); 
	int T=read();
	while(T--)Solve();
	return 0;
}
/*
1
7
7 1
8 2
9 7
7 7
8 5
9 6
10 2
2
9 1
11 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 15800kb

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: 2ms
memory: 15868kb

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
-1
3
16 36
25 7
17 39
6
7 5
8 11
5 5
6 4
4 9
3 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 16064kb

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 276
126 214
187 433
224 393
261 468
274 67
277 189
311 455
390 308
440 179
453 251
11 4
38 25
240 35
52 67
57 139
292 177
271 186
278 272
415...

result:

ok ok 2 cases (2 test cases)

Test #4:

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

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:

8
89287395 441913072
142917372 582720392
263974835 468188690
543529670 152471389
773363571 482933266
142917373 582720391
142917373 598813561
647691664 598813561
7
808969359 818037531
808969359 386523246
808969359 891229782
808969360 354711322
92745430 358274214
469117951 762966373
59832704 871951216...

result:

ok ok 20 cases (20 test cases)

Test #5:

score: 0
Accepted
time: 2ms
memory: 15904kb

input:

2
184
35763790 435860426
152681166 443483111
261932524 745277126
261932524 787982418
314305867 342102981
314305867 522593781
314305867 747023891
314305867 811404535
314305867 816914009
314305867 857896659
319901983 797458033
321347896 342102981
332550928 902179526
343207116 914408792
350635050 15515...

output:

160
314305867 787982418
350635050 435860426
350635050 811404535
407380694 797458033
469496529 342102981
469496529 438907614
469496529 732085440
469496529 816914009
469496529 837963933
495537855 461654555
496813081 699021890
496813081 787982418
496813081 815487777
496813081 857896659
520115644 751818...

result:

ok ok 2 cases (2 test cases)

Test #6:

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

input:

2
193
78368109 329329995
87932514 657474465
87932514 903492853
94608574 845872655
103602204 88649154
124431127 405860533
145262472 108198774
145262472 907127202
154400439 136367504
165270984 773451933
184157521 409828915
197728547 291882089
197728547 609623645
211750768 843867422
246178069 108396139...

output:

145
145262472 903492853
197728547 409828915
246178069 291882089
291242118 564718673
365329221 136367504
365329221 211655411
365329221 405860533
365329221 657489855
365329221 773451933
365329221 845872655
382558552 984789430
385064292 502303728
391226954 843867422
410833945 564718673
412106895 135814...

result:

ok ok 2 cases (2 test cases)

Test #7:

score: 0
Accepted
time: 2ms
memory: 15892kb

input:

2
192
1075648 579875717
1075648 937648715
1393060 191616432
3957616 541362608
3957616 971879257
5415801 541362608
5887448 541362608
5887448 624842533
25767120 610618164
26193206 214214028
26193206 231445627
26727662 374314271
29550509 755417826
29550509 917592925
30033126 610618164
31134588 58188305...

output:

131
31134588 231445627
33207011 541362608
46425938 755417826
250896470 264208611
295641139 541362608
333807226 762642201
340743563 288390629
341366249 231445627
360971009 755417826
417168695 231445627
417966308 381919591
418600362 755417826
429088204 541362608
509798823 541362608
509798823 741119775...

result:

ok ok 2 cases (2 test cases)

Test #8:

score: -100
Time Limit Exceeded

input:

20
14
378192988 147499872
378192988 837331700
449924898 147499872
449924898 837331700
592684636 147499872
592684636 837331700
783332532 147499872
783332532 837331700
378192988 197547597
783332532 197547597
378192988 343857831
783332532 343857831
378192988 576579017
783332532 576579017
2
449924898 19...

output:


result: