QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#786620#7696. Forest for the TreeshighkjAC ✓13ms3948kbC++112.1kb2024-11-26 22:28:292024-11-26 22:28:34

Judging History

This is the latest submission verdict.

  • [2024-11-26 22:28:34]
  • Judged
  • Verdict: AC
  • Time: 13ms
  • Memory: 3948kb
  • [2024-11-26 22:28:29]
  • Submitted

answer

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
#define x first
#define y second
typedef pair<int,int> pii;
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
const int ba=1331;
unordered_set<int> s;
int getid(const pair<int,int>&A){
	return (A.x)*ba+A.y;
}
pair<int,int> operator+(const pair<int,int> &A,const pair<int,int> &B){
	return make_pair(A.first+B.first,A.second+B.second);	
}
pair<int,int> operator-(const pair<int,int> &A,const pair<int,int> &B){
	return make_pair(A.first-B.first,A.second-B.second);	
}
const int N=5e3+10;
int n,m,R,T=1;
pii a[N],b[N];
void solve() {
	in(n),in(m),in(R);
	rep(i,1,n) in(a[i].x),in(a[i].y);
	rep(i,1,m) in(b[i].x),in(b[i].y);
	rep(i,1,n) s.insert(getid(a[i]));
	int cnt=0;
	int ansx=0,ansy=0;
	rep(dir,0,3){
		pii mn=b[1];
		rep(i,1,m) if(b[i].x<mn.x||(b[i].x==mn.y&&b[i].y<mn.y)) mn=b[i];
		rep(i,1,n){
			pii O=a[i]-mn;
			if(s.find(getid(O))!=s.end()) continue;
			bool flag=1;
			rep(j,1,m){
				if(!s.count(getid(O+b[j]))){
					flag=0;
					break;	
				}
			}
			if(!flag) continue;
			int cc=0;
			rep(j,1,n){
				int d=abs(O.x-a[j].x)+abs(O.y-a[j].y);
				if(d<=R) cc++;	
			}
			if(cc!=m) continue;
			cnt++;
			ansx=O.x;
			ansy=O.y;
		}
		rep(i,1,m){
			swap(b[i].x,b[i].y);
			b[i].y=-b[i].y;	
		}
	}
	if (cnt==0) cout<<"Impossible"<<endl;	
	else if (cnt==1) cout<<ansx<<' '<<ansy<<endl;
	else cout<<"Ambiguous"<<endl;
}
fire main(){
	while(T--){
		solve();
	}
	return false;	
}

详细

Test #1:

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

input:

4 4 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2
-2 3

output:

0 1

result:

ok single line: '0 1'

Test #2:

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

input:

4 4 4
0 1
1 0
0 -1
-1 0
0 1
1 0
0 -1
-1 0

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #3:

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

input:

4899 957 32
-9961 -9999
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
...

output:

-9929 -9959

result:

ok single line: '-9929 -9959'

Test #4:

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

input:

4899 941 40
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
-10000 -9955...

output:

Impossible

result:

ok single line: 'Impossible'

Test #5:

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

input:

4899 940 40
-9970 -9968
-9942 -9986
-9991 -9991
-9950 -9990
-9958 -9994
-9939 -9944
-9992 -9987
-9973 -9937
-9981 -9941
-9940 -9940
-9989 -9945
-9961 -9963
-9970 -9932
-9969 -9967
-9977 -9971
-9949 -9989
-9958 -9958
-9957 -9993
-9937 -9935
-9938 -9980
-9965 -9997
-9992 -9951
-9946 -9984
-10000 -9955...

output:

Impossible

result:

ok single line: 'Impossible'

Test #6:

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

input:

3 3 1000
1 0
0 1
1 1
1 0
0 1
1 1

output:

0 0

result:

ok single line: '0 0'

Test #7:

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

input:

5000 2 1000
0 0
1000 1000
66740 84615
-16851 37613
31009 31589
-68041 -71122
21568 86889
53743 -31217
-73472 63365
9594 -12742
-25497 -5264
15942 13442
19537 -83361
93129 67319
-27565 73861
75273 -19266
-55048 -79726
-45975 -36987
-51309 35820
-99049 -10933
-45867 99815
-52121 99729
-89976 -15892
38...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #8:

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

input:

5000 3 1000
0 0
1000 1000
1000 999
13954 9751
75888 -54632
10747 -12901
37707 -37988
-49564 26056
-30528 -9620
6227 -95560
-82768 85135
-15530 89254
-39739 -79664
-81590 -75580
91135 -20238
-52264 -66253
-41259 -90627
-7096 -35158
-67316 13384
79722 57595
-40566 99205
35854 -48598
-83531 -59472
-286...

output:

600 400

result:

ok single line: '600 400'

Test #9:

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

input:

4 3 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2

output:

Impossible

result:

ok single line: 'Impossible'

Test #10:

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

input:

3 3 100
1 1
2 1
3 1
0 1
0 2
0 3

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #11:

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

input:

4 3 2
1 1
2 2
2 1
3 3
0 1
0 2
-1 1

output:

2 0

result:

ok single line: '2 0'

Test #12:

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

input:

121 121 50
4 0
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 ...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #13:

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

input:

120 120 50
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 2
4 ...

output:

5 5

result:

ok single line: '5 5'

Test #14:

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

input:

120 119 50
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 2
4 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #15:

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

input:

121 121 50
4 0
-10 10
8 0
0 -4
-6 10
-8 -8
10 6
2 2
-8 10
-4 -8
6 2
-2 -2
-10 -6
-4 10
4 2
-6 -6
10 -10
8 2
0 -2
-8 -6
2 4
-4 -6
6 4
-2 0
-10 -4
-6 -4
10 -8
8 4
0 0
-8 -4
-4 -4
6 6
-2 2
-10 -2
-6 -2
10 -6
2 -10
0 2
-8 -2
6 -10
-4 -2
4 -10
-2 4
-10 0
8 -10
-6 0
2 -8
-8 0
6 -8
10 8
-4 0
-10 2
8 -8
-6 ...

output:

Ambiguous

result:

ok single line: 'Ambiguous'

Test #16:

score: 0
Accepted
time: 13ms
memory: 3700kb

input:

2598 217 20
-28 50
-36 46
-16 24
-24 20
50 6
-44 -38
42 2
6 48
-42 8
-50 4
-30 -18
-38 -22
-20 26
-18 -44
-38 14
2 50
-46 10
-18 -8
22 28
-26 -12
14 24
-34 -16
-6 -34
-14 -38
26 -2
-22 -42
18 -6
-4 12
36 48
-12 8
8 -14
48 22
0 -18
18 30
-8 -22
20 -40
12 -44
30 4
4 -48
-8 14
12 -8
4 -12
44 24
24 -34
...

output:

5 5

result:

ok single line: '5 5'