QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625828 | #9412. Stop the Castle | Oo | WA | 1ms | 3624kb | C++20 | 4.1kb | 2024-10-09 21:17:55 | 2024-10-09 21:17:59 |
Judging History
answer
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define i128 __int128
#define db long double
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
const int N = 310;
//const int M=;
//const int inf=(int)1e9;
//const ll INF=(ll)1e18;
int T, n, m;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
vector<int> g[N];
pair<int, int> a[N];
pair<int, int> L[N], R[N];
int Left, Right;
int match[N];
bool vis[N];
bool dfs(int x) {
for(auto v : g[x]) {
if(!vis[v]) {
vis[v] = 1;
if(!match[v] || dfs(match[v])) {
match[v] = x;
return true;
}
}
}
return false;
}
void solve() {
n = read();
Left = Right = 0;
for(int i = 1; i <= n; i++) g[i].clear();
memset(match, 0, sizeof(match));
map<int, vector<int>> r0, c0, r1, c1;
map<pair<int, int>, int> id;
for(int i = 1; i <= n; i++) {
int R = read(), C = read();
a[i] = {R, C};
id[{R, C}] = i;
r0[R].pb(C);
c0[C].pb(R);
}
m = read();
for(int i = 1; i <= m; i++) {
int R = read(), C = read();
r1[R].pb(C);
c1[C].pb(R);
}
for(auto &[_, v] : r0) sort(v.begin(), v.end());
for(auto &[_, v] : c0) sort(v.begin(), v.end());
for(auto &[_, v] : r1) sort(v.begin(), v.end());
for(auto &[_, v] : c1) sort(v.begin(), v.end());
for(auto &[row, v] : r0) {
if(v.size() <= 1) continue;
for(int i = 0; i + 1 < v.size(); i++) {
int l = v[i], r = v[i + 1];
if(r - l == 1) {
cout << "-1";
return;
}
auto check = [&]() {
if(r1.find(row) == r1.end()) return true;
auto &V = r1[row];
auto it = upper_bound(V.begin(), V.end(), l);
if(it == V.end()) return true;
assert(*it != r);
return *it > r;
};
if(check()) L[++Left] = {id[{row,l}], id[{row, r}]};
}
}
for(auto &[col, v] : c0) {
if(v.size() <= 1) continue;
for(int i = 0; i + 1 < v.size(); i++) {
int l = v[i], r = v[i + 1];
if(r - l == 1) {
cout << "-1";
return;
}
auto check = [&]() {
if(c1.find(col) == c1.end()) return true;
auto &V = c1[col];
auto it = upper_bound(V.begin(), V.end(), l);
if(it == V.end()) return true;
assert(*it != r);
return *it > r;
};
if(check()) R[++Right] = {id[{l,col}], id[{r, col}]};
}
}
// cout << "left:\n";
// for(int i = 1; i <= Left; i++) cout << L[i].fi << ' ' << L[i].se << '\n';
// cout << "right:\n";
// for(int i = 1; i <= Right; i++) cout << R[i].fi << ' ' << R[i].se << '\n';
// cout << '\n';
// cout << "debug:\n";
for(int i = 1; i <= Left; i++)
for(int j = 1; j <= Right; j++) {
auto [a1, a2] = L[i];
auto [b1, b2] = R[j];
// assert(a[a1].fi == a[a2].fi);
// assert(a[b1].se == a[b2].se);
if(a[a1].se < a[b1].se && a[b1].se < a[a2].se &&
a[b1].fi < a[a1].fi && a[a1].fi < a[b2].fi) g[i].pb(j);
}
int cnt = 0;
for(int i = 1; i <= Left; i++) {
memset(vis, 0, sizeof(vis));
if(dfs(i)) cnt++;
}
// cout << Left + Right - cnt << '\n';
vector<bool> okl(Left + 1), okr(Right + 1);
vector<pair<int, int>> ans;
for(int i = 1; i <= Right; i++) {
if(match[i]) {
int l = match[i], r = i;
okl[l] = 1, okr[r] = 1;
int x = L[l].fi, y = R[r].fi;
// cout << "match " << x << ' ' << y <<'\n';
ans.pb({a[x].fi, a[y].se});
}
}
for(int i = 1; i <= Left; i++) {
if(okl[i]) continue;
int x = L[i].fi;
ans.pb({a[x].fi, a[x].se + 1});
}
for(int i = 1; i <= Right; i++) {
if(okr[i]) continue;
int y = R[i].fi;
ans.pb({a[y].fi + 1, a[y].se});
}
assert(ans.size() == Left + Right - cnt);
cout << ans.size() << '\n';
for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
signed main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout<<fixed<<setprecision();
int T = read();
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
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: 3600kb
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 -13 16 36 25 7 17 39 6 5 5 8 9 6 4 7 3 3 10 2 11
result:
wrong answer Integer parameter [name=K] equals to -13, violates the range [-1, 256] (test case 19)