QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#523710 | #1142. Fountain Parks | green_gold_dog# | 0 | 537ms | 54000kb | C++20 | 3.3kb | 2024-08-18 16:40:51 | 2024-08-18 16:40:51 |
Judging History
answer
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll construct_roads(vector<ll> x, vector<ll> y) {
ll n = x.size();
if (n == 1) {
build(vector<ll>(0), vector<ll>(0), vector<ll>(0), vector<ll>(0));
return 1;
}
map<pair<ll, ll>, ll> all;
for (ll i = 0; i < n; i++) {
all[make_pair(x[i], y[i])] = i;
}
vector<vector<ll>> to(n);
vector<ll> m1;
for (ll i = 0; i < n; i++) {
bool bx = false, by = false;
if (all.find(make_pair(x[i] + 2, y[i])) != all.end()) {
bx = true;
to[i].push_back(all[make_pair(x[i] + 2, y[i])]);
}
if (all.find(make_pair(x[i], y[i] + 2)) != all.end()) {
by = true;
to[i].push_back(all[make_pair(x[i], y[i] + 2)]);
}
if (all.find(make_pair(x[i] - 2, y[i])) != all.end()) {
bx = true;
to[i].push_back(all[make_pair(x[i] - 2, y[i])]);
}
if (all.find(make_pair(x[i], y[i] - 2)) != all.end()) {
by = true;
to[i].push_back(all[make_pair(x[i], y[i] - 2)]);
}
if (to[i].empty()) {
return 0;
}
if (bx && by) {
m1.push_back(i);
}
}
set<pair<ll, ll>> have;
vector<ll> u, v, a, b;
for (ll i = 0; i < n; i++) {
for (auto j : to[i]) {
if (have.find(make_pair(j, i)) != have.end() || have.find(make_pair(i, j)) != have.end()) {
continue;
}
u.push_back(i);
v.push_back(j);
have.emplace(i, j);
ll bx = (x[i] + x[j]) / 2, by = (y[i] + y[j]) / 2;
ll add = 1;
if ((x[i] + y[i]) % 4 == 0) {
add = -add;
}
if (x[i] == x[j]) {
add = -add;
if (y[i] < y[j]) {
add = -add;
}
bx += add;
} else {
if (x[i] < x[j]) {
add = -add;
}
by += add;
}
a.push_back(bx);
b.push_back(by);
}
}
build(u, v, a, b);
return 1;
}
#ifdef LOCAL
static void check(bool cond, string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
check(!build_called, "build is called more than once");
build_called = true;
m = u.size();
check(int(v.size()) == m, "u.size() != v.size()");
check(int(a.size()) == m, "u.size() != a.size()");
check(int(b.size()) == m, "u.size() != b.size()");
_u = u;
_v = v;
_a = a;
_b = b;
}
int main() {
assert(scanf("%d", &n) == 1);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
build_called = false;
const int possible = construct_roads(x, y);
check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
if (possible == 1) {
check(build_called, "construct_roads() returned 1 without calling build()");
} else {
check(!build_called, "construct_roads() called build() but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
printf("%d\n", m);
for (int j = 0; j < m; j++) {
printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
}
}
fclose(stdout);
return 0;
}
#endif
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3724kb
input:
ba73dbf9c7d5e5202834d6a500541c 1 2 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 0
result:
ok
Test #2:
score: 5
Accepted
time: 0ms
memory: 3832kb
input:
ba73dbf9c7d5e5202834d6a500541c 2 2 2 2 4
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 1 0 1 1 3
result:
ok
Test #3:
score: 5
Accepted
time: 0ms
memory: 4072kb
input:
ba73dbf9c7d5e5202834d6a500541c 2 2 2 2 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #4:
score: 5
Accepted
time: 0ms
memory: 3904kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 2 2 2 4 2 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 1 1 3 1 2 3 5
result:
ok
Test #5:
score: 5
Accepted
time: 0ms
memory: 3864kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 2 2 4 2 6 2 8
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 3 0 1 1 3 1 2 3 5 2 3 1 7
result:
ok
Test #6:
score: 5
Accepted
time: 0ms
memory: 3800kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 2 2 2 4 2 8
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 2 2 4 2 8 2 10
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 1 1 3 2 3 3 9
result:
wrong answer Given structure is not connected: There is no path between vertices 0 and 2
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #82:
score: 20
Accepted
time: 0ms
memory: 3824kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 200000 2 200000 4 199998 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 1 200001 3 0 2 199999 3
result:
ok
Test #83:
score: 20
Accepted
time: 0ms
memory: 3776kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 200000 200000 200000 199998 199998 200000
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 2 199999 199999 0 1 200001 199999
result:
ok
Test #84:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
input:
ba73dbf9c7d5e5202834d6a500541c 12 2 2 2 4 4 2 2 200000 2 199998 4 200000 200000 2 200000 4 199998 2 200000 200000 200000 199998 199998 200000
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 8 0 2 3 3 0 1 1 3 3 5 3 199999 3 4 1 199999 6 7 200001 3 6 8 199999 3 9 11 199999 199999 9 10 200001 199999
result:
wrong answer Given structure is not connected: There is no path between vertices 0 and 3
Subtask #5:
score: 0
Wrong Answer
Test #108:
score: 20
Accepted
time: 423ms
memory: 48624kb
input:
ba73dbf9c7d5e5202834d6a500541c 200000 82422 100002 100002 52498 82816 2 97624 2 100002 58032 20638 100002 100002 7646 80512 2 2 10584 28426 100002 2 83036 2 64556 47872 100002 55196 2 85350 100002 2 95376 2 23942 12488 100002 83178 2 2 9086 85598 2 100002 78820 100002 10868 98810 2 84182 100002 2 71...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 200000 0 168975 82423 100003 0 148989 82421 100001 1 117727 100001 52499 1 67645 100003 52497 2 142334 82817 1 2 150926 82815 3 3 141442 97625 1 3 164963 97623 3 4 66537 100003 58033 4 9204 100001 58031 5 10116 20639 100003 5 106842 20637 100001 6 131543...
result:
ok
Test #109:
score: 20
Accepted
time: 415ms
memory: 48804kb
input:
ba73dbf9c7d5e5202834d6a500541c 199999 10674 50002 7228 2 31566 50002 48790 2 87212 50002 100002 76172 54282 100002 2 33136 100002 78564 50002 9882 50848 50002 50002 83692 92422 100002 100002 78880 100002 71432 50002 65586 3750 2 50002 11898 50002 17296 50002 44774 3836 2 49936 50002 50002 48536 1542...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 200000 0 113011 10675 50003 0 28598 10673 50001 1 161862 7229 1 1 28885 7227 3 2 171672 31567 50003 2 195414 31565 50001 3 185959 48791 3 3 41810 48789 1 4 38022 87213 50001 4 83724 87211 50003 5 12634 100003 76173 5 196759 100001 76171 6 127644 54283 10...
result:
ok
Test #110:
score: 20
Accepted
time: 448ms
memory: 49776kb
input:
ba73dbf9c7d5e5202834d6a500541c 199996 47612 97612 29284 20722 30860 80858 2350 52348 49558 99558 33234 83232 9050 59048 92420 57584 4174 54172 42730 92728 72144 77860 69182 19182 77286 72716 43440 6566 57918 7918 35822 85822 24864 25142 87024 37024 96744 46746 29472 79472 28650 78648 26748 76746 253...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 199996 0 98733 47613 97613 0 58294 47613 97611 1 154430 29283 20723 1 54701 29283 20721 2 102768 30861 80859 2 32658 30859 80859 3 28722 2351 52349 3 104033 2349 52349 4 71657 49559 99559 4 36906 49559 99557 5 98107 33235 83233 5 83246 33233 83233 6 1993...
result:
ok
Test #111:
score: 20
Accepted
time: 537ms
memory: 54000kb
input:
ba73dbf9c7d5e5202834d6a500541c 196096 266 878 52 818 34 890 674 450 960 390 446 622 224 138 794 360 22 436 234 760 126 336 454 434 672 386 286 36 94 134 736 774 782 752 1014 692 228 594 778 878 550 1008 246 732 588 250 982 460 786 76 342 404 2 68 58 174 230 282 604 358 700 438 274 156 94 324 706 948...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 261120 0 108894 267 879 0 19723 265 879 0 168561 265 877 0 170763 267 877 1 36004 53 817 1 20029 51 819 2 128182 35 891 2 162524 33 891 2 152677 33 889 2 73180 35 889 3 188238 675 451 3 14140 673 451 3 115072 673 449 3 130172 675 449 4 187463 961 389 4 2...
result:
ok
Test #112:
score: 20
Accepted
time: 412ms
memory: 44900kb
input:
ba73dbf9c7d5e5202834d6a500541c 175280 382 334 666 902 752 406 992 1306 1252 256 252 422 762 1018 72 210 1078 102 478 1182 1392 68 942 530 180 252 152 1176 2 594 52 182 522 1032 482 1386 242 260 242 276 112 572 782 138 762 1034 532 586 222 160 232 236 914 392 172 1006 612 1258 1170 832 1236 992 1370 ...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 194600 0 60502 381 335 0 108584 383 333 1 76116 667 903 1 64711 665 901 2 105943 753 407 2 113581 751 405 3 139936 993 1307 3 58325 991 1305 4 119978 1251 257 4 60050 1253 255 5 30972 253 421 5 109445 253 423 5 24116 251 423 5 164014 251 421 6 141680 761...
result:
ok
Test #113:
score: 20
Accepted
time: 0ms
memory: 3800kb
input:
ba73dbf9c7d5e5202834d6a500541c 7 183572 142078 183572 142080 183568 142076 183574 142078 183574 142076 183568 142078 183570 142078
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 6 0 3 183573 142077 0 1 183573 142079 0 6 183571 142079 2 5 183567 142077 3 4 183575 142077 5 6 183569 142077
result:
ok
Test #114:
score: 20
Accepted
time: 56ms
memory: 10660kb
input:
ba73dbf9c7d5e5202834d6a500541c 31065 186080 21286 185980 21532 185748 21002 185714 21252 185436 20722 186236 21564 185932 21236 185414 20700 185944 21578 185658 20936 185856 21540 186034 21122 186020 21492 186014 21310 185282 20638 185482 20878 185224 20682 185670 21264 186032 21510 186004 21112 185...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 34451 0 24707 186081 21285 0 14676 186079 21287 0 25501 186079 21285 1 8222 185981 21533 1 13964 185979 21531 2 987 185749 21001 2 22370 185747 21003 3 25665 185715 21251 3 13657 185713 21251 4 4646 185437 20721 4 21012 185435 20723 5 24651 186235 21565 ...
result:
ok
Test #115:
score: 0
Wrong Answer
time: 27ms
memory: 8256kb
input:
ba73dbf9c7d5e5202834d6a500541c 20000 70262 161716 35896 78638 36020 78778 35780 78778 70374 161892 35858 78838 35908 78680 70376 161802 35886 78784 35858 78886 70436 161842 35884 78716 36030 78752 70344 161912 70270 161766 35868 78870 70276 161828 35806 78664 70330 161764 35978 78806 35850 78718 703...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 23792 0 19387 70263 161715 0 9988 70263 161717 1 3013 35897 78637 1 6810 35895 78639 2 9602 36019 78777 3 18860 35781 78777 3 14236 35779 78779 3 4445 35779 78777 4 4281 70375 161891 5 9896 35859 78839 5 13963 35857 78839 5 10185 35859 78837 6 10158 3590...
result:
wrong answer Given structure is not connected: There is no path between vertices 0 and 1
Subtask #6:
score: 0
Skipped
Dependency #1:
0%