QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523713#1142. Fountain Parksgreen_gold_dog#45 558ms54896kbC++203.5kb2024-08-18 16:45:072024-08-18 16:45:08

Judging History

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

  • [2024-08-18 16:45:08]
  • 评测
  • 测评结果:45
  • 用时:558ms
  • 内存:54896kb
  • [2024-08-18 16:45:07]
  • 提交

answer

#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

struct DSU {
	vector<ll> p;
	DSU(ll n) {
		p.resize(n);
		for (ll i = 0; i < n; i++) {
			p[i] = i;
		}
	}
	ll get(ll a) {
		return (p[a] == a ? a : p[a] = get(p[a]));
	}
	void unite(ll a, ll b) {
		p[get(a)] = get(b);
	}
};

ll construct_roads(vector<ll> x, vector<ll> y) {
	ll n = x.size();
	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 (bx && by) {
			m1.push_back(i);
		}
	}
	set<pair<ll, ll>> have;
	vector<ll> u, v, a, b;
	DSU d(n);
	for (ll i = 0; i < n; i++) {
		for (auto j : to[i]) {
			d.unite(i, j);
			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);
		}
	}
	set<ll> aa;
	for (ll i = 0; i < n; i++) {
		aa.insert(d.get(i));
	}
	if (aa.size() > 1) {
		return 0;
	}
	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

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3768kb

input:

ba73dbf9c7d5e5202834d6a500541c
1
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
0

result:

ok 

Test #2:

score: 5
Accepted
time: 0ms
memory: 3804kb

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: 3744kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #4:

score: 5
Accepted
time: 0ms
memory: 3816kb

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: 3796kb

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: 3864kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #7:

score: 5
Accepted
time: 0ms
memory: 3772kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 8
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #8:

score: 5
Accepted
time: 0ms
memory: 3792kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 6
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #9:

score: 5
Accepted
time: 168ms
memory: 26376kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 15660
2 23918
2 132200
2 117654
2 162750
2 183010
2 75554
2 29740
2 185476
2 135138
2 194024
2 182274
2 1338
2 42922
2 51616
2 171196
2 159598
2 136432
2 84454
2 61806
2 136968
2 167442
2 150036
2 23974
2 10064
2 86342
2 146274
2 174318
2 130832
2 118838
2 180...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 86548 3 15661
0 30345 1 15659
1 29124 1 23919
1 55755 3 23917
2 68290 3 132201
2 13438 1 132199
3 9859 1 117655
3 13368 3 117653
4 67987 1 162751
4 23781 3 162749
5 24499 1 183011
5 79051 3 183009
6 5988 1 75555
6 12841 3 75553
7 68430 3 29741
7 ...

result:

ok 

Test #10:

score: 5
Accepted
time: 9ms
memory: 5956kb

input:

ba73dbf9c7d5e5202834d6a500541c
10000
2 3124
2 3126
2 3128
2 3130
2 3132
2 3134
2 3136
2 3138
2 3140
2 3142
2 3144
2 3146
2 3148
2 3150
2 3152
2 3154
2 3156
2 3158
2 3160
2 3162
2 3164
2 3166
2 3168
2 3170
2 3172
2 3174
2 3176
2 3178
2 3180
2 3182
2 3184
2 3186
2 3188
2 3190
2 3192
2 3194
2 3196
2 31...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
9999
0 1 3 3125
1 2 1 3127
2 3 3 3129
3 4 1 3131
4 5 3 3133
5 6 1 3135
6 7 3 3137
7 8 1 3139
8 9 3 3141
9 10 1 3143
10 11 3 3145
11 12 1 3147
12 13 3 3149
13 14 1 3151
14 15 3 3153
15 16 1 3155
16 17 3 3157
17 18 1 3159
18 19 3 3161
19 20 1 3163
20 21 3 ...

result:

ok 

Test #11:

score: 5
Accepted
time: 62ms
memory: 16096kb

input:

ba73dbf9c7d5e5202834d6a500541c
53891
2 3566
2 3568
2 3570
2 3572
2 3574
2 3576
2 3578
2 3580
2 3582
2 3584
2 3586
2 3588
2 3590
2 3592
2 3594
2 3596
2 3598
2 3600
2 3602
2 3604
2 3606
2 3608
2 3610
2 3612
2 3614
2 3616
2 3618
2 3620
2 3622
2 3624
2 3626
2 3628
2 3630
2 3632
2 3634
2 3636
2 3638
2 36...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
53890
0 1 1 3567
1 2 3 3569
2 3 1 3571
3 4 3 3573
4 5 1 3575
5 6 3 3577
6 7 1 3579
7 8 3 3581
8 9 1 3583
9 10 3 3585
10 11 1 3587
11 12 3 3589
12 13 1 3591
13 14 3 3593
14 15 1 3595
15 16 3 3597
16 17 1 3599
17 18 3 3601
18 19 1 3603
19 20 3 3605
20 21 1...

result:

ok 

Test #12:

score: 5
Accepted
time: 11ms
memory: 7064kb

input:

ba73dbf9c7d5e5202834d6a500541c
14979
2 4954
2 4956
2 4958
2 4960
2 4962
2 4964
2 4966
2 4968
2 4970
2 4972
2 4974
2 4976
2 4978
2 4980
2 4982
2 4984
2 4986
2 4988
2 4990
2 4992
2 4994
2 4996
2 4998
2 5000
2 5002
2 5004
2 5006
2 5008
2 5010
2 5012
2 5014
2 5016
2 5018
2 5020
2 5022
2 5024
2 5026
2 50...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
14978
0 1 1 4955
1 2 3 4957
2 3 1 4959
3 4 3 4961
4 5 1 4963
5 6 3 4965
6 7 1 4967
7 8 3 4969
8 9 1 4971
9 10 3 4973
10 11 1 4975
11 12 3 4977
12 13 1 4979
13 14 3 4981
14 15 1 4983
15 16 3 4985
16 17 1 4987
17 18 3 4989
18 19 1 4991
19 20 3 4993
20 21 1...

result:

ok 

Test #13:

score: 5
Accepted
time: 41ms
memory: 12480kb

input:

ba73dbf9c7d5e5202834d6a500541c
44171
2 36500
2 36502
2 36504
2 36506
2 36508
2 36510
2 36512
2 36514
2 36516
2 36518
2 36520
2 36522
2 36524
2 36526
2 36528
2 36530
2 36532
2 36534
2 36536
2 36538
2 36540
2 36542
2 36544
2 36546
2 36548
2 36550
2 36552
2 36554
2 36556
2 36558
2 36560
2 36562
2 36564...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #14:

score: 5
Accepted
time: 1ms
memory: 4300kb

input:

ba73dbf9c7d5e5202834d6a500541c
1000
2 20406
2 20378
2 37840
2 37702
2 20448
2 37688
2 37780
2 20720
2 38256
2 20612
2 38050
2 20152
2 37880
2 20116
2 20030
2 20526
2 38324
2 20956
2 20852
2 20356
2 37668
2 20292
2 37648
2 20320
2 20078
2 38060
2 38014
2 37738
2 37878
2 20336
2 20472
2 20214
2 38340
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #15:

score: 5
Accepted
time: 2ms
memory: 4196kb

input:

ba73dbf9c7d5e5202834d6a500541c
2000
2 19578
2 1754
2 1760
2 130946
2 164378
2 1038
2 20302
2 131788
2 131632
2 164392
2 19868
2 164924
2 131380
2 130972
2 131348
2 1070
2 131568
2 19492
2 19876
2 131606
2 1142
2 1588
2 1424
2 1726
2 131416
2 946
2 20158
2 19574
2 20106
2 1736
2 1186
2 19476
2 164256...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #16:

score: 5
Accepted
time: 179ms
memory: 26072kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 103034
2 75068
2 69976
2 84860
2 113488
2 156808
2 109250
2 119184
2 169250
2 182382
2 161594
2 169232
2 41046
2 87158
2 10192
2 32612
2 84228
2 49708
2 157912
2 160028
2 160234
2 167142
2 22010
2 37360
2 64100
2 113388
2 81460
2 52862
2 77902
2 155958
2 13330...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 21451 1 103035
0 22204 3 103033
1 23594 3 75069
1 41977 1 75067
2 35896 3 69977
2 89253 1 69975
3 19303 3 84861
3 83859 1 84859
4 98266 3 113489
4 99175 1 113487
5 4928 3 156809
5 98562 1 156807
6 66778 1 109251
6 45395 3 109249
7 94027 3 119185
...

result:

ok 

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #17:

score: 0
Wrong Answer
time: 0ms
memory: 3840kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
4 4
2 4
4 2
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 1 3 3
0 2 5 3
1 3 1 3
2 3 3 3

result:

wrong answer Tree @(3, 3) appears more than once: for edges on positions 0 and 3

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 20
Accepted

Test #82:

score: 20
Accepted
time: 0ms
memory: 4088kb

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: 3796kb

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: 20
Accepted
time: 0ms
memory: 3808kb

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
0

result:

ok 

Test #85:

score: 20
Accepted
time: 449ms
memory: 50672kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
195232 4772
192370 7632
64282 135722
174444 25558
54846 145156
70170 129832
196228 3774
23234 176768
186862 13140
22458 177546
18158 181846
144902 55100
109692 90310
154220 45782
180406 19598
176744 23260
69098 130906
83308 116694
728 199274
143272 56730
17012 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 183397 195231 4771
0 114192 195233 4771
1 137403 192371 7631
1 172969 192371 7633
2 127552 64281 135721
2 183528 64283 135721
3 110702 174445 25557
3 136306 174445 25559
4 24147 54847 145155
4 81542 54847 145157
5 14273 70171 129831
5 175852 701...

result:

ok 

Test #86:

score: 20
Accepted
time: 482ms
memory: 50412kb

input:

ba73dbf9c7d5e5202834d6a500541c
199997
56858 56864
1456 1462
51406 51410
89266 89272
53562 53556
80164 80158
13970 13966
41960 41966
48338 48342
98766 98772
82904 82898
38168 38172
28780 28774
38142 38146
16616 16612
15258 15262
69676 69672
85410 85416
59306 59310
712 718
6144 6140
61280 61286
28928 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199996
0 69117 56859 56863
0 178618 56857 56863
1 94816 1457 1461
1 164263 1455 1461
2 10313 51405 51411
2 47909 51405 51409
3 138138 89267 89271
3 181819 89265 89271
4 195085 53563 53557
4 176501 53561 53557
5 117046 80165 80159
5 90488 80163 80159
6 72...

result:

ok 

Test #87:

score: 20
Accepted
time: 468ms
memory: 50380kb

input:

ba73dbf9c7d5e5202834d6a500541c
199997
65538 34474
61104 38910
57364 42638
29768 70236
50488 49524
91868 8146
42764 57238
16096 83906
17718 82294
91644 8368
90818 9186
83908 16096
97246 2756
68350 31652
53514 46498
10854 89158
64174 35838
62258 37746
36734 63280
76516 23496
19968 80036
2764 97240
559...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199996
0 4262 65539 34475
0 31471 65537 34475
1 135770 61103 38911
1 75395 61103 38909
2 12192 57365 42637
2 97792 57365 42639
3 154870 29767 70235
3 186447 29769 70235
4 163528 50489 49525
4 36676 50487 49525
5 122132 91867 8147
5 191484 91867 8145
6 67...

result:

ok 

Test #88:

score: 20
Accepted
time: 373ms
memory: 42468kb

input:

ba73dbf9c7d5e5202834d6a500541c
169995
97050 40000
83488 40000
83726 40000
100000 25052
100000 13668
2 904
60986 40000
28594 20000
51184 40000
40000 12506
92936 2
32440 40000
61562 2
29342 2
29178 2
31564 2
84020 2
22850 2
86310 40000
2 25682
67964 20000
27174 2
34700 40000
100000 18902
24042 20000
8...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
169994
0 48803 97051 39999
0 149070 97049 40001
1 91806 83489 40001
1 49792 83487 39999
2 107485 83727 39999
2 38800 83725 40001
3 23935 99999 25053
3 76844 100001 25051
4 127847 99999 13669
4 128104 100001 13667
5 28879 3 905
5 140016 1 903
6 85621 6098...

result:

ok 

Test #89:

score: 20
Accepted
time: 268ms
memory: 33732kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
1314 1854
274 822
298 698
1510 1034
958 1170
938 878
558 406
1442 1542
1394 734
546 1234
1018 1426
1206 1454
414 402
210 566
1578 426
230 278
1022 1102
462 1026
166 66
1374 1810
1334 202
314 1042
602 1658
1598 550
718 1650
186 1618
1062 1806
262 1614
1082 1950
9...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #90:

score: 20
Accepted
time: 491ms
memory: 43128kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
194 138
778 1194
636 506
688 34
322 418
332 1882
706 574
106 746
162 1682
16 650
90 830
794 926
266 1642
468 914
790 438
354 1242
200 1530
706 402
482 822
612 1926
292 1934
224 662
172 1362
676 1294
344 1602
290 466
734 1238
300 1938
224 30
184 1370
520 822
264 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #91:

score: 20
Accepted
time: 438ms
memory: 43140kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
166 984
734 960
1026 70
1018 572
774 48
758 496
486 720
1090 680
862 120
1510 284
790 824
58 878
1102 690
910 256
322 140
6 750
630 554
86 506
122 898
1498 886
1266 110
470 514
114 832
338 182
1094 300
718 288
278 532
470 42
630 614
438 96
958 252
378 764
958 11...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #92:

score: 20
Accepted
time: 459ms
memory: 49484kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
1398 812
1458 624
1286 630
1430 638
1250 584
1026 92
1026 148
1114 750
38 642
1202 748
842 38
998 638
662 594
1570 430
710 258
26 552
154 442
10 666
922 378
90 488
1490 538
1594 662
1154 502
210 416
670 672
454 256
898 774
590 148
1318 842
1266 794
746 860
310 9...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 95131 1399 813
0 141453 1397 811
1 33099 1459 625
1 173051 1457 623
2 185399 1285 631
2 138067 1287 629
3 32622 1429 639
3 177627 1431 637
4 93378 1251 585
4 185453 1249 583
5 35313 1027 93
5 111374 1025 91
6 165035 1027 149
6 135827 1025 147
7 ...

result:

ok 

Test #93:

score: 20
Accepted
time: 447ms
memory: 49392kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
866 434
1150 510
298 342
1442 170
382 976
686 442
854 894
318 976
166 640
1562 246
1438 814
1382 872
1558 782
578 320
1378 474
1474 320
1590 628
1554 278
682 82
554 318
34 248
674 870
246 522
726 482
1390 920
1298 682
294 622
402 472
1198 742
614 264
598 630
910...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 139943 865 435
0 116856 867 433
1 190724 1149 511
1 195765 1151 509
2 141027 297 343
2 8284 299 341
3 12567 1441 171
3 197560 1443 169
4 182652 383 977
4 169426 381 975
5 191687 685 443
5 19779 687 441
6 117484 853 895
6 100077 855 893
7 35119 3...

result:

ok 

Test #94:

score: 20
Accepted
time: 538ms
memory: 49500kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
972 594
440 1198
762 586
426 1542
468 126
252 1434
182 1442
452 814
778 386
744 1118
854 82
912 178
84 1366
982 1202
212 1106
226 1442
210 878
570 890
422 846
264 1334
772 910
66 926
118 1094
304 98
810 1426
34 158
142 2
258 698
732 554
152 1110
290 490
794 690
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 19228 973 593
0 30935 971 595
1 99162 441 1197
1 26137 439 1199
2 50834 763 587
2 55334 761 585
3 69154 427 1543
3 70555 425 1541
4 110193 469 125
4 78949 467 127
5 86455 253 1433
5 56006 251 1435
6 40239 183 1443
6 35105 181 1441
7 119977 453 8...

result:

ok 

Test #95:

score: 20
Accepted
time: 530ms
memory: 49452kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
628 130
416 710
642 1042
500 138
150 202
294 166
742 1166
872 1094
854 378
500 846
72 490
122 10
328 422
54 834
340 1426
264 818
466 774
254 422
338 1554
952 542
238 1502
42 322
672 474
826 1246
994 1454
614 1418
816 386
314 346
620 1526
982 1298
296 1490
310 67...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 54663 629 129
0 89742 627 131
1 122356 417 709
1 79585 415 711
2 182975 643 1043
2 2195 641 1041
3 6362 501 137
3 146785 499 139
4 71412 151 203
4 10250 149 201
5 89919 295 167
5 107769 293 165
6 38065 743 1167
6 115392 741 1165
7 14587 873 1093...

result:

ok 

Test #96:

score: 20
Accepted
time: 0ms
memory: 3836kb

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 #97:

score: 20
Accepted
time: 18ms
memory: 6800kb

input:

ba73dbf9c7d5e5202834d6a500541c
14125
185792 20626
186256 20742
186128 20844
186294 20356
185902 20752
186302 20350
185884 20314
185894 20614
185980 20576
186148 20520
185830 20870
185858 20382
186108 20826
186204 20714
185822 20694
185928 20984
185768 20438
186176 20758
185926 20604
186106 20672
185...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
14124
0 8271 185793 20625
0 8570 185791 20627
1 4845 186257 20741
1 2012 186255 20743
2 11069 186129 20845
2 11721 186127 20843
3 4513 186295 20355
3 1052 186295 20357
4 2451 185901 20753
4 9250 185901 20751
5 13516 186303 20351
5 13517 186301 20351
5 47...

result:

ok 

Test #98:

score: 20
Accepted
time: 100ms
memory: 18456kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
177456 177456
171074 171074
168200 168200
161352 161352
67104 67104
118318 118318
52258 52258
922 922
48450 48450
198048 198048
78358 78358
25852 25852
190812 190812
55744 55744
100624 100624
67562 67562
100866 100866
151566 151566
150458 150458
89932 89932
1124...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #99:

score: 20
Accepted
time: 422ms
memory: 50432kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
36996 36996
186060 186060
138654 138654
119648 119648
77274 77274
155998 155998
126848 126846
40008 40008
131372 131372
176154 176154
52550 52550
28622 28620
152276 152274
163746 163744
77792 77790
26394 26392
107542 107542
137218 137218
99318 99318
123124 12312...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 140297 36997 36997
0 72651 36997 36995
1 73338 186061 186061
1 68639 186061 186059
2 167017 138655 138655
2 152379 138655 138653
3 18413 119649 119649
3 19259 119649 119647
4 137259 77275 77275
4 15516 77275 77273
5 1864 155999 155999
5 61025 15...

result:

ok 

Test #100:

score: 20
Accepted
time: 14ms
memory: 5684kb

input:

ba73dbf9c7d5e5202834d6a500541c
10000
176796 4336
103510 178630
176666 4270
176706 4416
176736 4434
176678 4446
176682 4352
176682 4328
103620 178604
176774 4284
176762 4278
176664 4418
103654 178692
176752 4376
176800 4358
176700 4426
103638 178626
176668 4434
103624 178694
103638 178756
103504 1786...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #101:

score: 20
Accepted
time: 88ms
memory: 13616kb

input:

ba73dbf9c7d5e5202834d6a500541c
50000
19712 125246
21028 78432
107586 175540
41632 93316
40222 19636
107864 175496
41542 93234
19724 125336
21004 78390
19840 125472
107696 175608
107744 175604
107868 175560
20950 78474
40432 19666
41542 93254
19828 125410
19672 125296
41694 93142
41650 93228
20986 78...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #102:

score: 20
Accepted
time: 195ms
memory: 23424kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
11532 82706
12484 8300
116672 115008
12586 8316
116574 115040
91278 196254
167350 193456
91178 196396
167250 193500
11696 82884
12456 8192
167330 193490
167264 193368
162872 76530
162838 76386
11692 82780
21684 51392
116554 115012
167308 193302
167246 193300
175...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #103:

score: 20
Accepted
time: 165ms
memory: 21952kb

input:

ba73dbf9c7d5e5202834d6a500541c
80000
110632 196678
110706 196562
110062 196474
110372 197130
110334 196998
110584 196940
110462 196562
110576 196678
110076 196620
110630 196486
110586 196562
110194 197046
110232 196526
110576 196778
110488 197020
110092 196852
110704 196558
110254 196698
110692 1966...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
79999
0 73852 110633 196677
0 45227 110631 196679
1 45001 110705 196563
1 5579 110707 196561
2 72219 110063 196475
2 61716 110061 196473
3 65550 110373 197129
3 73070 110373 197131
3 42497 110371 197131
4 78377 110333 196999
4 2538 110335 196997
5 30672 ...

result:

ok 

Test #104:

score: 20
Accepted
time: 230ms
memory: 28884kb

input:

ba73dbf9c7d5e5202834d6a500541c
110000
153248 86150
153422 86140
153336 85974
153374 85680
153026 85962
153322 85930
153536 85810
152996 86246
153750 85712
153536 86158
153790 86094
153098 85904
153182 85690
153078 86148
153848 86062
153656 85888
153066 85882
153096 85824
153554 85590
153518 86200
15...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
109999
0 31128 153249 86151
0 464 153247 86151
0 58369 153247 86149
1 71849 153423 86139
1 47814 153421 86141
2 4224 153337 85973
2 76461 153337 85975
2 71758 153335 85975
3 14569 153375 85681
4 50001 153027 85963
4 83687 153025 85963
4 109712 153027 859...

result:

ok 

Test #105:

score: 20
Accepted
time: 336ms
memory: 36196kb

input:

ba73dbf9c7d5e5202834d6a500541c
140000
182484 19098
182932 18626
183100 19106
183132 19482
182768 18952
183204 19426
182944 18630
183078 19558
182858 18640
183242 19530
183212 19092
183248 18828
183174 19230
183330 18848
183322 18710
182638 18824
183070 18818
182708 18952
183010 19154
183120 19540
18...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
139999
0 127229 182485 19097
0 13150 182483 19099
1 102899 182933 18625
1 32271 182933 18627
2 67421 183101 19105
2 46540 183099 19107
3 105231 183133 19483
3 59095 183131 19483
4 100508 182769 18953
4 111022 182767 18951
4 70591 182769 18951
5 77238 183...

result:

ok 

Test #106:

score: 20
Accepted
time: 398ms
memory: 42808kb

input:

ba73dbf9c7d5e5202834d6a500541c
170000
12466 152266
12366 152380
12874 152026
12384 151764
12674 151762
12364 151662
12394 152198
13164 152022
12042 152002
12498 152164
12416 152346
12554 152040
12246 151920
12190 151820
12110 152452
12858 152564
12834 152132
13022 152014
12706 152692
12468 151568
12...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
169999
0 38497 12465 152265
0 138244 12467 152265
1 59298 12365 152381
2 88369 12875 152025
3 14820 12383 151765
3 101367 12383 151763
3 51246 12385 151763
4 154029 12675 151763
5 39948 12365 151661
5 141715 12365 151663
5 89491 12363 151663
5 93885 1236...

result:

ok 

Test #107:

score: 20
Accepted
time: 503ms
memory: 49816kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
121744 79484
121292 78880
120816 79608
121418 79068
121408 79102
121396 79782
121148 79636
121194 79636
121052 79024
120820 79454
121652 79184
121112 80116
121204 79382
121096 79926
121154 80104
121514 79848
121274 80028
121786 79584
120990 79962
121284 79608
12...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199999
0 58441 121745 79485
0 144130 121743 79483
0 134416 121745 79483
1 38015 121293 78879
2 103768 120817 79609
3 107175 121419 79067
3 121490 121417 79069
4 126324 121407 79103
4 149442 121407 79101
5 133820 121397 79781
6 79047 121147 79637
7 94456 ...

result:

ok 

Subtask #5:

score: 20
Accepted

Test #108:

score: 20
Accepted
time: 436ms
memory: 49696kb

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: 447ms
memory: 49612kb

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: 466ms
memory: 50384kb

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: 558ms
memory: 54896kb

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: 444ms
memory: 45688kb

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: 3808kb

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: 54ms
memory: 10828kb

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: 20
Accepted
time: 32ms
memory: 7644kb

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
0

result:

ok 

Test #116:

score: 20
Accepted
time: 133ms
memory: 18380kb

input:

ba73dbf9c7d5e5202834d6a500541c
70000
101734 41174
53110 85692
125290 151418
53092 85668
125240 151526
101728 41006
155882 162620
70032 179926
125070 151314
69944 179838
125086 151362
101720 41088
125220 151418
78622 142762
70006 179900
78714 142782
53076 85646
78466 142806
156134 162652
69884 179760...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #117:

score: 20
Accepted
time: 268ms
memory: 28692kb

input:

ba73dbf9c7d5e5202834d6a500541c
120000
81980 29184
45086 128478
45130 128460
34094 161734
34312 161616
6660 133698
45032 128422
6464 133838
77706 149488
29744 82012
34066 161698
34152 161602
67876 16558
81992 29244
41026 168276
6594 133820
6410 133690
34300 161660
172610 38842
172506 38750
40990 1682...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #118:

score: 20
Accepted
time: 227ms
memory: 28148kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
21246 185820
20976 186272
21262 185900
20648 185812
21086 186086
20868 185712
21114 185810
21262 186168
20684 185892
20982 186216
20922 186194
21206 185654
20762 185796
21248 186200
21142 185850
21060 185510
20926 185746
21326 185710
20948 185798
21056 185958
21...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
119656
0 7360 21247 185821
0 74580 21245 185821
0 47260 21245 185819
1 26560 20977 186273
1 84678 20975 186273
1 80494 20977 186271
2 33027 21263 185899
2 22031 21263 185901
2 27098 21261 185899
3 1271 20647 185813
3 37851 20649 185811
4 654 21087 186087...

result:

ok 

Test #119:

score: 20
Accepted
time: 311ms
memory: 34672kb

input:

ba73dbf9c7d5e5202834d6a500541c
125000
143578 113244
143620 112756
143600 113284
143670 113030
143848 113452
143654 113456
144176 112896
143982 112746
143648 112962
143542 113182
143954 113258
143500 112982
143960 113170
144016 112808
143802 112736
143952 112846
143364 112900
143658 112576
143632 112...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
149635
0 42763 143579 113243
0 91943 143579 113245
0 19939 143577 113245
1 119521 143621 112757
1 69215 143619 112755
2 124313 143601 113285
2 8634 143599 113283
3 76772 143669 113031
3 28245 143671 113029
4 87356 143847 113453
4 42370 143847 113451
5 94...

result:

ok 

Test #120:

score: 20
Accepted
time: 373ms
memory: 40980kb

input:

ba73dbf9c7d5e5202834d6a500541c
150000
115254 119710
115364 119296
115174 119288
115390 119648
115444 119620
115682 119260
115616 118782
114978 119008
115702 119260
115590 119250
115170 119030
115146 119308
115222 118958
114912 118972
115304 118678
115034 119388
115326 119348
115328 119082
115256 118...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
179481
0 45958 115255 119711
0 82102 115253 119711
0 107557 115255 119709
1 52386 115365 119297
1 113329 115363 119295
2 37295 115175 119289
2 83038 115173 119289
2 56672 115173 119287
3 53498 115391 119647
3 137177 115391 119649
3 37998 115389 119649
4 ...

result:

ok 

Test #121:

score: 20
Accepted
time: 455ms
memory: 47232kb

input:

ba73dbf9c7d5e5202834d6a500541c
175000
70684 45878
70722 45914
70572 45804
70996 46520
70150 46340
70360 46792
70818 45802
70460 46280
70946 46002
70154 46322
70894 46696
70710 46696
70120 46212
71042 46286
70194 46302
70624 45856
70434 46158
70936 46408
70870 46012
70790 45822
70470 45956
70136 4644...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
209652
0 171874 70685 45877
0 27595 70685 45879
0 163275 70683 45879
1 122120 70723 45915
1 46778 70721 45915
2 150635 70571 45805
2 10296 70573 45803
3 93810 70997 46521
3 32548 70997 46519
4 12312 70151 46339
4 40741 70149 46341
4 63614 70149 46339
5 4...

result:

ok 

Test #122:

score: 20
Accepted
time: 547ms
memory: 53524kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
120832 79932
121178 79254
120936 79156
121624 79142
121168 79430
121456 79722
121398 79244
121684 79344
121242 79718
121204 79394
121244 79174
121382 78964
121072 79288
121126 79078
121494 79378
121472 79306
121074 79832
121140 79956
121018 80010
121332 79428
12...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
239462
0 4288 120833 79933
0 34396 120831 79933
0 26581 120831 79931
1 137656 121177 79255
1 50809 121179 79253
2 46533 120937 79157
2 131126 120935 79157
2 159993 120937 79155
3 64399 121625 79141
3 85658 121625 79143
3 134566 121623 79141
4 93530 12116...

result:

ok 

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%