QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#759701 | #9412. Stop the Castle | zq500 | WA | 1ms | 3648kb | C++14 | 2.3kb | 2024-11-18 11:20:57 | 2024-11-18 11:20:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n, m;
unordered_map<int, vector<pair<int, int>>>hang, lie;
cin>>n;
for(int i=1, x, y; i<=n; i++)
{
cin>>x>>y;
hang[x].push_back({y, 1});
lie[y].push_back({x, 1});
}
cin>>m;
for(int i=1, x, y; i<=m; i++)
{
cin>>x>>y;
hang[x].push_back({y, 0});
lie[y].push_back({x, 0});
}
vector<array<int, 3>> boy, girl;
bool ugly = 0;
for(auto& [x, vec] : hang)
{
sort(vec.begin(), vec.end());
for(int j = 1; j < vec.size(); ++j)
{
auto& [y1, op1] = vec[j - 1];
auto& [y2, op2] = vec[j];
if(op1 && op2)
{
if(y1 + 1 == y2) ugly = 1;
boy.push_back({ x, y1, y2 });
}
}
}
for(auto& [y, vec] : lie)
{
sort(vec.begin(), vec.end());
for(int j = 1; j < vec.size(); ++j)
{
auto& [x1, op1] = vec[j - 1];
auto& [x2, op2] = vec[j];
if(op1 && op2)
{
if(x1 + 1 == x2) ugly = 1;
girl.push_back({ y, x1, x2 });
}
}
}
n = boy.size(), m = girl.size();
vector<vector<int>> E(n);
for(int u = 0; u < n; ++u)
{
auto& [x, y1, y2] = boy[u];
for(int v = 0; v < m; ++v)
{
auto& [y, x1, x2] = girl[v];
if(x1 < x && x < x2 && y1 < y && y < y2)
{
E[u].push_back(v);
}
}
}
if(ugly)
{
printf("-1\n");
return;
}
vector<int> npy(m, -1);
for(int u = 0; u < n; ++u)
{
vector<int> vis(m, 0);
function<bool(int)> dfs = [&](int u) -> bool
{
for(auto& v : E[u])
{
if(vis[v]) continue;
vis[v] = 1;
if(npy[v] == -1 || dfs(npy[v]))
{
npy[v] = u;
return true;
}
}
return false;
};
dfs(u);
}
vector<pair<int, int>> res;
vector<int> happy(n, false);
for(int v = 0; v < m; ++v)
{
if(npy[v] != -1)
{
happy[npy[v]] = true;
res.emplace_back(boy[npy[v]][0], girl[v][0]);
}
else
{
auto& [y, x1, x2] = girl[v];
res.emplace_back(x1 + x2 >> 1, y);
}
}
for(int u = 0; u < n; ++u)
{
if(!happy[u])
{
auto& [x, y1, y2] = boy[u];
res.emplace_back(x, y1 + y2 >> 1);
}
}
cout<<res.size()<<"\n";
for(auto& [x, y] : res)
{
cout<<x<<" "<<y<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tn=1;
cin>>tn;
while(tn--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
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 4 6 2 3 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
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 35 38 24 12 37 18 5 21 6 23 26 35 50 16 11 16 31 0 1 29 10 0 1 43 28 5 42 44 1 7 1 26 33 28 44 45 0 5 9 1 26 15 29 33 27 41 44 21 1 32 10 0 0 0 0 6 23 10 29 46 35 34 23 44 12 25 29 27 0 3 32 17 20 30 43 28 0 3 24 39 16 36 25 9 6 8 11 6 10 6 9 7 5 6 5 5 5 -1
result:
wrong answer There are still 4 pairs of castles which can attack each other (test case 19)