QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#813155 | #9412. Stop the Castle | CirnoNine | WA | 1ms | 4004kb | C++23 | 5.8kb | 2024-12-13 22:34:43 | 2024-12-13 22:34:59 |
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);
break;
}
}
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);
break;
}
}
}
}
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: 3504kb
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: 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 5 12 6 16 10 16 15 20 26 34 50 0 1 16 10 0 1 43 22 5 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 6 12 11 23 44 24 46 29 21 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:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 4004kb
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 278 272 138 429 187 433 224 393 240 35 261 468 271 186 274 67 277 189 11 4 286 367 311 455 380 385 390 308 415 305 440 179 453 251 35 276 52 67 57 139 39 477 21 499 38 25 19 436 199 432 260 275 311 177 306 374 187 467 154 496 52 139 393 307 126 214 349 61 334 367 352 112 270 356 277 305 280 186 1...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3784kb
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 142917373 582720391 142917372 582720392 142917373 598813561 263974835 468188690 543529670 152471389 647691664 598813561 773363571 482933266 7 59832704 871951216 92745430 358274214 469117951 762966373 808969360 354711322 808969359 386523246 808969359 891229782 808969359 818037531...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3696kb
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...
output:
160 496813082 902179526 561219907 328140562 673102149 356915105 561219907 112860541 556513262 421876106 556513261 342102982 556513262 342102981 673102149 445858067 673102150 902179526 701933830 492168300 702209411 335551846 702209412 342102981 496813081 902179527 561219908 342102981 702209411 342102...
result:
wrong answer Participant's answer is 137, but jury has better answer 136 (test case 2)