QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787199 | #7696. Forest for the Trees | Shunpower | AC ✓ | 131ms | 4160kb | C++17 | 2.3kb | 2024-11-27 10:22:36 | 2024-11-27 10:22:37 |
Judging History
answer
//Author:Leftist_G / Shunpower
//Cloud Island & Rain Temperature
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld long double
#define il inline
#define ptc putchar
using namespace std;
const int N=5e3+10;
int nt,ns,rm;
pii dot[N];
pii dxy[N];
map <pii,int> p;
vector <pair<pii,int>> ans;
void calc(int op){
fr1(i,1,nt){
pii pos=mp(dot[i].fi-dxy[1].fi,dot[i].se-dxy[1].se);
if(p.count(pos)) continue;
// cout<<pos.fi<<" "<<pos.se<<endl;
vector <int> chk;
vector <int> tem;
fr1(j,1,ns){
pii newp=mp(pos.fi+dxy[j].fi,pos.se+dxy[j].se);
if(!p.count(newp)) goto label;
else chk.pb(p[newp]);
}
// for(auto i:chk) cout<<i<<endl;
fr1(j,1,nt){
if(abs(dot[j].fi-pos.fi)+abs(dot[j].se-pos.se)<=rm) tem.pb(j);
}
// for(auto i:tem) cout<<i<<endl;
sort(chk.begin(),chk.end());
if(chk==tem) ans.pb(mp(pos,op));
label:
continue;
}
}
int main(){
#ifdef Shun
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin>>nt>>ns>>rm;
fr1(i,1,nt) cin>>dot[i].fi>>dot[i].se,p[dot[i]]=i;
fr1(i,1,ns) cin>>dxy[i].fi>>dxy[i].se;
{
calc(1);
}
{
fr1(i,1,ns) dxy[i].fi*=-1,dxy[i].se*=-1;
calc(2);
fr1(i,1,ns) dxy[i].fi*=-1,dxy[i].se*=-1;
}
{
fr1(i,1,ns) swap(dxy[i].fi,dxy[i].se),dxy[i].fi*=-1;
calc(3);
fr1(i,1,ns) dxy[i].fi*=-1,swap(dxy[i].fi,dxy[i].se);
}
{
fr1(i,1,ns) swap(dxy[i].fi,dxy[i].se),dxy[i].se*=-1;
calc(4);
fr1(i,1,ns) dxy[i].se*=-1,swap(dxy[i].fi,dxy[i].se);
}
if(ans.empty()) return cout<<"Impossible\n",0;
sort(ans.begin(),ans.end());
ans.resize(unique(ans.begin(),ans.end())-ans.begin());
if(ans.size()!=1) cout<<"Ambiguous\n";
else cout<<ans[0].fi.fi<<" "<<ans[0].fi.se<<'\n';
ET;
}
//ALL FOR Zhang Junhao.
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3796kb
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: 24ms
memory: 4160kb
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: 6ms
memory: 3916kb
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: 5ms
memory: 3852kb
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: 3804kb
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: 9ms
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: 9ms
memory: 3912kb
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: 3768kb
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: 3624kb
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: 3760kb
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: 3564kb
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: 1ms
memory: 3848kb
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: 3852kb
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: 1ms
memory: 3616kb
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: 131ms
memory: 3736kb
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'