QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#523710#1142. Fountain Parksgreen_gold_dog#0 537ms54000kbC++203.3kb2024-08-18 16:40:512024-08-18 16:40:51

Judging History

你现在查看的是最新测评结果

  • [2024-08-18 16:40:51]
  • 评测
  • 测评结果:0
  • 用时:537ms
  • 内存:54000kb
  • [2024-08-18 16:40:51]
  • 提交

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%