QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#813146 | #9412. Stop the Castle | CirnoNine | WA | 1ms | 3816kb | C++23 | 5.7kb | 2024-12-13 22:30:57 | 2024-12-13 22:30:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
struct Line{
int x1,y1,x2,y2;
int cnt = 0;
int id;
bool operator<(Line t) {
return cnt<t.cnt;
}
};
void solve() {
int n;
cin >> n;
vector<pii> a,b;
vector<int> vtX,vtY;
map<int,int> mpX,mpY;
for (int i = 0; i < n; i++) {
int x,y;
cin >> x >> y;
vtX.push_back(x);
vtY.push_back(y);
a.push_back({x,y});
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int x,y;
cin >> x >> y;
vtX.push_back(x);
vtY.push_back(y);
b.push_back({x,y});
}
sort(vtX.begin(),vtX.end());
int szX = unique(vtX.begin(),vtX.end())-vtX.begin();
for (int i = 0; i < szX; i++) mpX[vtX[i]] = i;
sort(vtY.begin(),vtY.end());
int szY = unique(vtY.begin(),vtY.end())-vtY.begin();
for (int i = 0; i < szY; i++) mpY[vtY[i]] = i;
vector<vector<int>> mp(szX,vector<int>(szY,0));
for (auto [x,y] : a) {
int x2 = mpX[x];
int y2 = mpY[y];
mp[x2][y2] = 1;
}
for (auto [x,y] : b) {
int x2 = mpX[x];
int y2 = mpY[y];
mp[x2][y2] = 2;
}
vector<Line> vtL;
for (int i = 0; i < szX; i++) {
for (int j = 0; j < szY; j++) {
if (mp[i][j] != 1) continue;
for (int x = i+1; x < szX; x++) {
if (mp[x][j] == 2) break;
if (mp[x][j] == 1) {
Line line;
line.x1 = min(i,x);
line.x2 = max(i,x);
line.y1 = j;
line.y2 = j;
vtL.push_back(line);
}
}
for (int y = j+1; y < szY; y++) {
if (mp[i][y] == 2) break;
if (mp[i][y] == 1) {
Line line;
line.x1 = i;
line.x2 = i;
line.y1 = min(j,y);
line.y2 = max(j,y);
vtL.push_back(line);
}
}
}
}
vector<vector<int>> lines(vtL.size());
vector<bool> check(n+9,1);
for (int i = 0; i < vtL.size(); i++) {
auto [x1,y1,x2,y2,s1,_] = vtL[i];
vtL[i].id = i;
for (int j = i+1; j < vtL.size(); j++) {
auto [x3,y3,x4,y4,s2,__] = vtL[j];
if (x1 == x2 && y3 == y4) {
if (y1 < y3 && y3 < y2 && x3 < x1 && x1 < x4) {
vtL[i].cnt++;
vtL[j].cnt++;
lines[i].push_back(j);
lines[j].push_back(i);
}
}
else if (y1 == y2 && x3 == x4) {
if (y3 < y1 && y1 < y4 && x1 < x3 && x3 < x2) {
vtL[i].cnt++;
vtL[j].cnt++;
lines[i].push_back(j);
lines[j].push_back(i);
}
}
}
}
vector<pii> ans;
auto vtL2 = vtL;
sort(vtL.begin(),vtL.end());
for (auto line : vtL) {
auto [x1,y1,x2,y2,s1,id] = line;
// cerr << "line:\n";
// cerr << vtX[x1] << " " << vtY[y1] << endl;
// cerr << vtX[x2] << " " << vtY[y2] << endl;
if (check[id] == 0) continue;
if (s1 == 0) { //无重叠
if (x1 == x2) {
int ry1 = vtY[y1];
int ry2 = vtY[y2];
if (ry2 - ry1 == 1) {
cout << -1 << endl;
return;
}
ans.push_back({vtX[x1],ry1+1});
}else {
int rx1 = vtX[x1];
int rx2 = vtX[x2];
if (rx2 - rx1 == 1) {
cout << -1 << endl;
return;
}
ans.push_back({rx1+1,vtY[y1]});
}
check[id] = 0;
}else {
int minCnt = 1000,minID = -1;
for (auto id2 : lines[id]) {
if (check[id2] == 0) continue;
if (vtL2[id2].cnt < minCnt) {
minCnt = vtL2[id2].cnt;
minID = id2;
}
}
if (minID == -1) { //无重叠
if (x1 == x2) {
int ry1 = vtY[y1];
int ry2 = vtY[y2];
if (ry2 - ry1 == 1) {
cout << -1 << endl;
return;
}
ans.push_back({vtX[x1],ry1+1});
}else {
int rx1 = vtX[x1];
int rx2 = vtX[x2];
if (rx2 - rx1 == 1) {
cout << -1 << endl;
return;
}
ans.push_back({rx1+1,vtY[y1]});
}
check[id] = 0;
continue;
}
//重叠
auto [x3,y3,x4,y4,s2,id2] = vtL2[minID];
if (x1 == x2 && y3 == y4) {
ans.push_back({vtX[x1],vtY[y3]});
}
else if (y1 == y2 && x3 == x4) {
ans.push_back({vtX[x3],vtY[y1]});
}
check[id] = 0;
check[id2] = 0;
}
}
cout << ans.size() << endl;
for (auto [x,y] : ans) {
cout << x << " " << y << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int i = 0; i < t; i++) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
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: 3628kb
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 6 12 6 16 10 16 10 16 15 20 26 34 50 0 1 16 10 0 1 43 22 6 1 3 1 3 1 13 33 10 42 44 44 45 0 5 8 1 21 15 27 41 29 26 44 4 1 32 9 0 0 0 0 7 12 11 23 44 24 46 29 21 23 10 23 10 35 34 0 3 20 30 31 17 43 25 0 -1 3 17 39 25 7 16 36 6 8 11 3 10 4 9 5 5 6 4 7 3
result:
wrong answer Duplicated position (16, 10) (test case 2)