QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794936 | #9412. Stop the Castle | XiaoretaW | WA | 1ms | 3632kb | C++20 | 4.4kb | 2024-11-30 16:56:56 | 2024-11-30 16:57:04 |
Judging History
answer
#include <bits/stdc++.h>
#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
void solve(){
int n; cin >> n;
map<int, vector<int>> rowA, colA;
map<int, vector<int>> rowB, colB;
for(int i = 0; i < n; i++){
int r, c; cin >> r >> c;
rowA[r].push_back(c);
colA[c].push_back(r);
}
map<pii, int> ob;
int m; cin >> m;
for(int i = 0; i < m; i++){
int r, c; cin >> r >> c;
rowB[r].push_back(c);
colB[c].push_back(r);
ob[{r, c}] = 1;
}
int id = 0, L = 0;
map<int, int> to;
map<pii, int> belx;
map<pii, int> bely;
for(auto&[r, posx]: rowA){
sort(all(posx));
int num = posx.size();
for(int i = 0; i < num - 1; i++){
to[++id] = r;
belx[{posx[i], posx[i + 1]}] = id;
}
}
L = id;
for(auto&[c, posy]: colA){
sort(all(posy));
int num = posy.size();
for(int i = 0; i < num - 1; i++){
to[++id] = c;
bely[{posy[i], posy[i + 1]}] = id;
}
}
vector<vector<int>> adj(L + 1);
for(auto&[r, posx]: rowA){
int numx = posx.size();
for(int i = 0; i < numx - 1; i++){
if(posx[i] + 1 == posx[i + 1]){
cout << -1 << '\n';
return;
}
for(auto&[c, posy]: colA){
int numy = posy.size();
for(int j = 0; j < numy - 1; j++){
if(posy[j] + 1 == posy[j + 1]){
cout << -1 << '\n';
return;
}
if(posy[j] < r and posy[j + 1] > r and posx[i] < c and posx[i + 1] > c){
int u = belx[{posx[i], posx[i + 1]}];
int v = bely[{posy[j], posy[j + 1]}];
adj[u].push_back(v);
}
}
}
}
}
vector<int> st(id + 1), match(id + 1);
function<bool(int)> find = [&](int u){
for(int v: adj[u]){
if(!st[v]){
st[v] = true;
if(match[v] == 0 or find(match[v])){
match[v] = u;
return true;
}
}
}
return false;
};
for(int i = 1; i <= L; i++){
st.assign(id + 1, false);
find(i);
}
vector<pii> ans;
for(int u = L + 1; u <= id; u++){
if(match[u]){
int r = to[match[u]];
int c = to[u];
if(!ob.count({r, c})){
rowB[r].push_back(c);
colB[c].push_back(r);
ans.push_back({r, c});
}
}
}
// debug(ans);
for(auto&[_, vec]: rowB){
sort(all(vec));
}
for(auto&[_, vec]: colB){
sort(all(vec));
}
for(auto&[r, vec]: rowA){
int num = vec.size();
for(int i = 0; i < num - 1; i++){
if(vec[i + 1] == vec[i] + 1){
cout << -1 << '\n';
return;
}
auto it = upper_bound(all(rowB[r]), vec[i]);
int posr = vec[i + 1];
if(it == rowB[r].end() or *it > posr){
ans.push_back({r, vec[i] + 1});
}
}
}
for(auto&[c, vec]: colA){
int num = vec.size();
for(int i = 0; i < num - 1; i++){
if(vec[i + 1] == vec[i] + 1){
cout << -1 << '\n';
return;
}
auto it = upper_bound(all(colB[c]), vec[i]);
int posr = vec[i + 1];
if(it == colB[c].end() or *it > posr){
ans.push_back({vec[i] + 1, c});
}
}
}
cout << ans.size() << '\n';
for(auto[x, y]: ans){
cout << x << ' ' << y << '\n';
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while(T--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
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: 0
Accepted
time: 1ms
memory: 3632kb
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 6 5 5 8 9 6 4 7 3 3 10 2 11
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3632kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 224 35 94 61 349 61 91 67 393 112 132 138 52 139 185 147 154 153 126 160 311 177 352 186 126 275 277 305 270 356 334 367 306 374 199 432 187 467 154 496 35 276 187 433 224 393 260 223 261 468 274 67 277 189 311 455 390 308 440 179 453 251 11 4 38 25 240 35 52 67 57 139 271 186 278 272 415 305 391...
result:
wrong answer Participant's answer is 48, but jury has better answer 47 (test case 2)