QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#627296 | #9412. Stop the Castle | Luckyblock | WA | 1ms | 3868kb | C++20 | 3.6kb | 2024-10-10 15:29:05 | 2024-10-10 15:29:06 |
Judging History
answer
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 1e3 + 10;
const int kM = 2e5 + 10;
//=============================================================
int housenum, bannum, n, maxnode;
int edgenum, head[kN], v[kM], ne[kM];
struct Blank {
int l, r, id;
};
int temp;
std::vector<pii> ans;
std::map<pii, pii> point;
std::map<int, std::set<pii> > rhouse, chouse;
std::map<int, std::vector<Blank> > rnode, cnode;
int match[kN];
bool vis[kN];
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
bool init() {
std::cin >> housenum;
edgenum = 0;
n = 0, maxnode = 4 * housenum;
for (int i = 1; i <= maxnode; ++ i) head[i] = match[i] = 0;
ans.clear(), point.clear();
rhouse.clear(), chouse.clear(), rnode.clear(), cnode.clear();
for (int i = 1; i <= housenum; ++ i) {
int r, c; std::cin >> r >> c;
rhouse[r].insert(mp(c, 0));
chouse[c].insert(mp(r, 0));
}
std::cin >> bannum;
for (int i = 1; i <= bannum; ++ i) {
int r, c; std::cin >> r >> c;
rhouse[r].insert(mp(c, 1));
chouse[c].insert(mp(r, 1));
}
int flag = 0;
for (auto [r, s]: rhouse) {
int last = -1;
for (auto [c, type]: s) {
if (last != -1 && type == 0) {
flag |= (c == last + 1);
rnode[r].push_back((Blank){last + 1, c - 1, ++ n});
}
last = type ? -1 : c;
}
}
for (auto [c, s]: chouse) {
int last = -1;
for (auto [r, type]: s) {
if (last != -1 && type == 0) {
flag |= (r == last + 1);
cnode[c].push_back((Blank){last + 1, c - 1, ++ n});
}
last = type ? -1 : r;
}
}
if (flag) return true;
for (auto [r, sr]: rnode) {
for (auto [l1, r1, id1]: sr) {
for (auto [c, sc]: cnode) {
if (c < l1 || r1 < c) continue;
for (auto [l2, r2, id2]: sc) {
if (r < l2 || r2 < r) continue;
Add(id1, id2);
point[mp(id1, id2)] = mp(r, c);
}
}
}
}
return false;
}
bool dfs(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (vis[v_]) continue;
vis[v_] = 1;
if (!match[v_] || dfs(match[v_])) {
match[v_] = u_;
return 1;
}
}
return 0;
}
void solve() {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) vis[j] = 0;
dfs(i);
}
for (int i = 1; i <= n; ++ i) {
if (match[i]) {
ans.push_back(point[mp(match[i], i)]);
auto [r, c] = ans.back();
rhouse[r].insert(mp(c, 1));
chouse[c].insert(mp(r, 1));
}
}
temp = ans.size();
for (auto [r, s]: rhouse) {
int last = -1;
for (auto [c, type]: s) {
if (last != -1 && type == 0) {
ans.push_back(mp(r, c - 1));
}
last = type ? -1 : c;
}
}
for (auto [c, s]: chouse) {
int last = -1;
for (auto [r, type]: s) {
if (last != -1 && type == 0) {
ans.push_back(mp(r - 1, c));
}
last = type ? -1 : r;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
if (init()) {
// std::cout << -1 << "----\n";
std::cout << -1 << "\n";
continue;
}
solve();
std::cout << ans.size() << "\n";
for (auto [x, y]: ans) std::cout << x << " " << y << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
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: 3868kb
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 29 12 41 18 42 38 5 16 13 16 47 31 6 26 26 36 50 0 1 42 10 0 1 43 35 5 1 11 1 40 33 47 44 46 43 44 0 5 27 41 29 40 44 38 10 1 31 15 1 32 12 0 0 0 0 8 12 40 23 42 23 45 29 33 35 45 27 10 41 34 34 46 0 3 20 31 43 32 34 17 0 -1 3 16 36 25 12 31 39 7 8 11 5 5 6 6 7 7 8 5 9 9 10 10
result:
wrong answer Participant's answer is 8, but jury has better answer 6 (test case 15)