QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603813 | #9412. Stop the Castle | ucup-team3474 | WA | 2ms | 4652kb | C++20 | 5.3kb | 2024-10-01 19:28:12 | 2024-10-01 19:28:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=414,M=N*N;
int h[M],ne[M],e[M],idx;
int match[N];
int n1,n2,m;
int n;
bool tf[M];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x){
// cout<<x<<endl;
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(tf[j]==0){
tf[j]=1;
if(match[j]==0||find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
PII d[N],dd[N];
int g[214][214];
bool rowtf[214],coltf[214];
int lr[214],lc[214],rr[214],rc[214];
void __(){
cin>>n;
map<PII,int> mp;
for(int i=1;i<=n;i++){
cin>>d[i].first>>d[i].second;
mp[d[i]]=0;
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>dd[i].first>>dd[i].second;
mp[dd[i]]=1;
}
// cout<<114514<<endl;
memset(lr,0x3f,sizeof lr);
memset(rr,-0x3f,sizeof rr);
memset(lc,0x3f,sizeof lc);
memset(rc,-0x3f,sizeof rc);
memset(h,-1,sizeof h);
idx=0;
memset(rowtf,0,sizeof rowtf);
memset(coltf,0,sizeof coltf);
vector<int> row,col;
map<int,int> mpr,mpc;
row.push_back(-1e9);
col.push_back(-1e9);
for(int i=1;i<=n;i++){
row.push_back(d[i].first);
col.push_back(d[i].second);
}
sort(row.begin(),row.end());
row.erase(unique(row.begin(),row.end()),row.end());
for(int i=1;i<row.size();i++) mpr[row[i]]=i;
sort(col.begin(),col.end());
col.erase(unique(col.begin(),col.end()),col.end());
for(int i=1;i<col.size();i++) mpc[col[i]]=i;
for(int i=1;i<=n;i++){
int r1=mpr[d[i].first],c1=mpc[d[i].second];
lr[r1]=min(lr[r1],c1),rr[r1]=max(rr[r1],c1);
lc[c1]=min(lc[c1],r1),rc[c1]=max(rc[c1],r1);
}
memset(g,false,sizeof g);
for(int i=1;i<row.size();i++){
for(int j=1;j<col.size();j++){
PII zb={row[i],col[j]};
if(mp.count(zb)){
if(mp[zb]==1){
// cout<<"--"<<i<<" "<<j<<endl;
rowtf[i]=1;coltf[j]=1;
}
}else{
// cout<<i<<" "<<j<<" "<<row[i]<<" "<<col[j]<<endl;
g[i][j]=1;
}
}
}
n1=row.size()-1,n2=col.size()-1;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
if(rowtf[i]||coltf[j]||!g[i][j]) continue;
if(j>=lr[i]&&j<=rr[i]&&i>=lc[j]&&i<=rc[j]){
// cout<<i<<" "<<j<<" "<<row[i]<<" "<<col[j]<<endl;
add(i,j);
}
// cout<<i<<" "<<j<<endl;
}
}
// cout<<n1<<" "<<n2<<endl;
memset(match,0,sizeof match);
int res=0;
for(int i=1;i<=n1;i++){
memset(tf,false,sizeof tf);
// cout<<i<<endl;
if(find(i)) res++;
}
// cout<<14<<endl;
vector<PII> ans;
// cout<<n1<<endl;
for(int i=1;i<=n1;i++){
// cout<<i<<" ";
if(match[i]!=0){
int u=i,v=match[i];
// cout<<u<<" "<<v<<endl;
ans.push_back({row[u],col[v]});
mp[{row[u],col[v]}]=1;
rowtf[u]=1,coltf[v]=1;
}
}
// cout<<endl;
for(int i=1;i<=n1;i++){
if(rowtf[i]) continue;
int x=row[i],y=0x3f3f3f3f,mx=-0x3f3f3f3f;
// cout<<i<<endl;
bool flag=0;
y=col[lr[i]],mx=col[rr[i]];
if(mx==y) flag=1;
// cout<<y<<" "<<mx<<endl;
for(auto [xx,yy]:mp){
if(yy==1&&xx.first==x){
if(xx.second>y&&xx.second<mx) flag=1;
}
}
if(flag) continue;
while(y<=mx){
if(!mp.count({x,y})){
ans.push_back({x,y});
flag=1;
break;
}
y++;
}
// cout<<flag<<endl;
if(!flag){
cout<<-1<<"\n";
return;
}
}
// cout<<114514<<endl;
// cout<<n2<<endl;
for(int i=1;i<=n2;i++){
if(coltf[i]) continue;
int x=col[i],y=0x3f3f3f3f,mx=-0x3f3f3f3f;
bool flag=0;
// cout<<i<<" "<<lc[i]<<" "<<rc[i]<<endl;
y=row[lc[i]],mx=row[rc[i]];
// cout<<"--"<<y<<" "<<mx<<endl;
if(mx==y) flag=1;
for(auto [xx,yy]:mp){
// if(yy==1) cout<<xx.first<<" "<<xx.second<<endl;
if(yy==1&&xx.second==x){
// cout<<xx.first<<" "<<xx.second<<endl;
if(xx.first>y&&xx.first<mx) flag=1;
}
}
// cout<<endl;
// cout<<flag<<endl;
if(flag) continue;
while(y<=mx){
// cout<<y<<" "<<x<<endl;
if(!mp.count({y,x})){
ans.push_back({y,x});
flag=1;
break;
}
y++;
}
if(!flag){
cout<<-1<<"\n";
return;
}
}
cout<<ans.size()<<"\n";
for(auto [x,y]:ans) cout<<x<<" "<<y<<"\n";
// for(int i=0;i<214;i++) r[i].clear(),c[i].clear();
}
int main(){
// ios::sync_with_stdio(0);
int _;
cin>>_;
while(_--){
__();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4652kb
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: 2ms
memory: 4556kb
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 4 16 10 12 6 20 26 34 50 0 1 16 10 0 1 43 22 4 1 3 33 10 44 45 42 44 0 4 29 26 44 4 8 1 21 15 1 32 9 0 0 0 0 7 12 20 26 39 23 10 35 5 13 10 30 34 24 46 0 3 20 30 43 25 31 17 0 -1 5 34 7 16 3 25 7 8 36 17 39 8 5 5 11 8 6 4 7 3 8 2 4 9 3 10 2 11
result:
wrong answer There are still 1 pairs of castles which can attack each other (test case 2)