QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611861 | #9412. Stop the Castle | propane | WA | 1ms | 3764kb | C++20 | 3.7kb | 2024-10-04 23:19:30 | 2024-10-04 23:19:32 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;
int match[1005];
bool v[1005];
vector<int> g[1005];
bool find(int x){
for(auto j : g[x]){
if (!v[j]){
v[j] = true;
if (match[j] == -1 or find(match[j])){
match[j] = x;
match[x] = j;
return true;
}
}
}
return false;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
map<int, vector<int> > mp1, mp2;
for(int i = 0; i < n; i++){
int a, b;
cin >> a >> b;
mp1[a].push_back(b);
mp2[b].push_back(a);
}
int m;
cin >> m;
map<int, vector<int> > mp3, mp4;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
mp3[a].push_back(b);
mp4[b].push_back(a);
}
auto norm = [&](map<int, vector<int> > &mp){
for(auto &[x, v] : mp){
sort(v.begin(), v.end());
}
};
norm(mp1);
norm(mp2);
norm(mp3);
norm(mp4);
bool ok = true;
auto solve = [&](map<int, vector<int> > &mp1, map<int, vector<int> > &mp3, vector<array<int, 3> > &p){
auto check = [&](int x, int y1, int y2){
if (!mp3.contains(x)) return false;
auto &v = mp3[x];
auto it = upper_bound(v.begin(), v.end(), y1);
if (it != v.end() and *it < y2) return true;
return false;
};
for(auto &[x, v] : mp1){
for(int i = 0; i + 1 < v.size(); i++){
if (v[i] + 1 == v[i + 1]){
ok = false;
}
if (!check(x, v[i], v[i + 1])){
p.push_back({x, v[i], v[i + 1]});
}
}
}
};
vector<array<int, 3> > p1, p2;
solve(mp1, mp3, p1);
solve(mp2, mp4, p2);
if (!ok){
cout << -1 << '\n';
continue;
}
const int s1 = p1.size(), s2 = p2.size();
for(int i = 0; i < s1; i++){
auto [x, y1, y2] = p1[i];
for(int j = 0; j < s2; j++){
auto [y, x1, x2] = p2[j];
if (y > y1 and y < y2 and x > x1 and x < x2){
g[i].push_back(j + s1);
}
}
}
for(int i = 0; i < s1 + s2; i++){
match[i] = -1;
}
for(int i = 0; i < s1; i++){
for(int j = 0; j < s1 + s2; j++){
v[j] = false;
}
find(i);
}
vector<pair<int, int> > ans;
for(int i = 0; i < s1; i++){
if (match[i] != -1){
ans.push_back({p1[i][0], p2[match[i] - s1][0]});
}
}
for(int i = 0; i < s1; i++){
if (match[i] == -1){
auto [x, y1, y2] = p1[i];
ans.push_back({x, y1 + 1});
}
}
for(int i = 0; i < s2; i++){
if (match[i + s1] == -1){
auto [y, x1, x2] = p2[i];
ans.push_back({x1 + 1, y});
}
}
cout << ans.size() << '\n';
for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
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: 1ms
memory: 3764kb
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 5 5 -902226764 6 9 7 5 8 10 2 11
result:
wrong answer Integer parameter [name=y_i] equals to -902226764, violates the range [1, 10^9] (test case 21)