QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#612586 | #9412. Stop the Castle | wlh | WA | 0ms | 3800kb | C++17 | 4.0kb | 2024-10-05 12:09:15 | 2024-10-05 12:09:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define int long long
typedef pair<int,int> pr;
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const int N = 1e6+10;
string YES="YES",Yes="Yes",yes="yes",NO="NO",No="No",no="no";
const int mod=998244353,inf=1e15;
int dx[]={0,0,-1,0,1},dy[]={0,-1,0,1,0};
struct nb{
int x, y;
};
void shuchu(nb w){
cout << w.x << ' ' << w.y << ' ';
}
void solve()
{
int n, m;
cin >> n;
vector<nb>a(n + 1);
for(int i = 1; i <= n; i ++){
cin >> a[i].x >> a[i].y;
}
cin >> m;
vector<nb>b(m + 1), bx, by;
for(int i = 1; i <= m; i ++){
cin >> b[i].x >> b[i].y;
}
for(int i = 1; i <= n; i ++) b.push_back(a[i]);
vector<array<nb, 2>>vx, vy;
vector<nb>ans;
for(int i = 1; i <= n; i ++){
for(int j = i + 1; j <= n; j ++){
if(a[i].x == a[j].x){
int f = 1;
for(int k = 1; k <= n + m; k ++) if(b[k].x == a[i].x && min(a[i].y, a[j].y) < b[k].y && b[k].y < max(a[i].y, a[j].y)){
f = 0; break;
}
if(f == 0) continue;
if(a[i].y + 1 == a[j].y || a[j].y + 1 == a[i].y){
cout << -1 << endl;
return ;
}
if(a[i].y < a[j].y) vx.push_back({a[i], a[j]});
else vx.push_back({a[j], a[i]});
}
else if(a[i].y == a[j].y){
int f = 1;
for(int k = 1; k <= n + m; k ++) if(b[k].y == a[i].y && min(a[i].x, a[j].x) < b[k].x && b[k].x < max(a[i].x, a[j].x)){
f = 0; break;
}
if(f == 0) continue;
if(a[i].x + 1 == a[j].x || a[j].x + 1 == a[i].x){
cout << -1 << endl;
return ;
}
if(a[i].x < a[j].x) vy.push_back({a[i], a[j]});
else vy.push_back({a[j], a[i]});
}
}
}
// for(auto [x, y] : vx){
// shuchu(x), shuchu(y);
// cout << endl;
// }
// cout << endl;
// for(auto [x, y] : vy){
// shuchu(x), shuchu(y);
// cout << endl;
// }
int nx = vx.size(), ny = vy.size();
vector<vector<int>> vt(nx + 1);
for(int i = 0; i < nx ; i ++){
auto [x1, x2] = vx[i];
for(int j = 0; j < ny; j ++){
auto [y1, y2] = vy[j];
if(y1.x < x1.x && x1.x < y2.x && x1.y < y1.y && y1.y < x2.y){
vt[i].push_back(j);
}
}
}
vector<int>vis(nx + 1), match(ny + 1, -1);
auto dfs = [&](auto&& dfs, int u) -> int{
for(auto v:vt[u]){
if(!vis[v]){
vis[v] = 1;
if(match[v] == -1 || dfs(dfs, match[v])){
match[v] = u;
return 1;
}
}
}
return 1;
};
for(int i = 0; i < nx; i ++){
for(int j = 0; j < ny; j ++) vis[j] = 0;
dfs(dfs, i);
}
// for(int j = 0; j < ny; j ++) cout << match[j] << ' ';
// cout << endl;
vector<int>visx(nx);
for(int v = 0; v < ny; v ++){
auto [y1, y2] = vy[v];
if(match[v] != -1){
int u = match[v];
auto [x1, x2] = vx[u];
ans.push_back({x1.x, y1.y});
visx[u] = 1;
}
else{
ans.push_back({y1.x + 1, y1.y});
}
}
for(int i = 0; i < nx; i ++){
if(!visx[i]){
auto [x1, x2] = vx[i];
ans.push_back({x1.x, x1.y + 1});
}
}
cout << ans.size() << endl;
for(auto [x, y] : ans){
cout << x << ' ' << y << endl;
}
}
signed main()
{
ios;
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 0ms
memory: 3800kb
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 29 38 34 18 5 12 6 20 26 34 50 16 10 16 15 0 1 16 10 0 1 43 22 5 42 44 1 3 1 13 33 10 44 45 0 5 8 1 21 15 27 41 29 26 44 4 1 32 9 0 0 0 0 6 23 10 24 46 35 34 12 11 23 44 29 21 0 3 31 17 20 30 43 25 0 -1 3 16 36 17 39 25 7 7 8 5 4 9 3 10 2 11 5 5 6 4 7 3
result:
wrong answer Participant's answer is 7, but jury has better answer 6 (test case 21)