QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795234 | #9412. Stop the Castle | XiaoretaW | RE | 1ms | 3652kb | C++20 | 5.0kb | 2024-11-30 18:53:02 | 2024-11-30 18:53:03 |
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);
}
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);
}
for(auto&[_, vec]: rowB){
sort(all(vec));
}
for(auto&[_, vec]: colB){
sort(all(vec));
}
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);
set<pii> occ;
for(auto&[r, posx]: rowA){
int numx = posx.size();
for(int i = 0; i < numx - 1; i++){
auto it = upper_bound(all(rowB[r]), posx[i]);
int posr = posx[i + 1];
if(it == rowB[r].end() or *it > posr){
for(auto&[c, posy]: colA){
int numy = posy.size();
for(int j = 0; j < numy - 1; j++){
auto it2 = upper_bound(all(colB[c]), posy[j]);
int posr2 = posy[j + 1];
if(it2 == colB[c].end() or *it2 > posr2){
if(posy[j] < r and posy[j + 1] > r and posx[i] < c and posx[i + 1] > c){
occ.insert({r, c});
int u = belx[{posx[i], posx[i + 1]}];
int v = bely[{posy[j], posy[j + 1]}];
to[u] = r;
to[v] = c;
assert(to[u] == r and to[v] == c);
assert(u < v && u <= L && v > L);
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] = 1;
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 + 3, 0);
find(i);
}
vector<pii> ans;
for(int u = L + 1; u <= id; u++){
if(match[u]){
assert(match[u] <= L);
int r = to[match[u]];
int c = to[u];
// debug(occ, r, c);
assert(occ.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: 0ms
memory: 3640kb
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: 3648kb
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: 0
Accepted
time: 1ms
memory: 3640kb
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:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 89287395 441913072 142917372 582720392 263974835 468188690 543529670 152471389 773363571 482933266 142917373 582720391 142917373 598813561 647691664 598813561 7 808969359 818037531 808969359 386523246 808969359 891229782 808969360 354711322 92745430 358274214 469117951 762966373 59832704 871951216...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: -100
Runtime Error
input:
2 184 35763790 435860426 152681166 443483111 261932524 745277126 261932524 787982418 314305867 342102981 314305867 522593781 314305867 747023891 314305867 811404535 314305867 816914009 314305867 857896659 319901983 797458033 321347896 342102981 332550928 902179526 343207116 914408792 350635050 15515...