QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32159#28. Corporate life (after hostile takover)Qingyu100 ✓275ms54968kbC++232.2kb2022-05-17 21:39:362022-05-17 21:39:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 21:39:39]
  • 评测
  • 测评结果:100
  • 用时:275ms
  • 内存:54968kb
  • [2022-05-17 21:39:36]
  • 提交

answer

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	struct graph_t {
		std::vector<int> dfn, siz;
		std::vector<std::vector<int>> adj;
		int tot;
		graph_t (int n) {
			dfn = std::vector<int>(n, 0);
			siz = std::vector<int>(n, 1);
			adj = std::vector(n, std::vector<int>());
			for (int i = 1; i < n; ++i) {
				int fa;
				std::cin >> fa;
				--fa;
				adj[fa].emplace_back(i);
			}
			tot = 0;
			auto dfs = [&](auto &self, int x) -> void {
				dfn[x] = tot++;
				for (int y : adj[x]) {
					self(self, y);
					siz[x] += siz[y];
				}
			};
			dfs(dfs, 0);
		}
	} F(n), G(n);
	struct query_t {
		int id, x, y, coef;
		query_t(int id, int x, int y, int coef) : id(id), x(x), y(y), coef(coef) {

		}
		bool operator<(const query_t &rhs) const {
			return x < rhs.x;
		}
	};
	struct fenwick_t {
		std::vector<int> t;
		static constexpr int lowbit(int x) { return x & -x; }
		void add(int p, int v) {
			++p;
			for (; p < t.size(); p += lowbit(p))
				t[p] += v;
		}
		int query(int p) {
			++p;
			int r = 0;
			for (; p; p -= lowbit(p))
				r += t[p];
			return r;
		}
		fenwick_t(int n) {
			t = std::vector<int>(n + 1, 0);
		}
	} tr(n);
	std::vector<std::pair<int, int>> points;
	for (int i = 0; i < n; ++i) {
		points.emplace_back(F.dfn[i], G.dfn[i]);
	}
	std::sort(points.begin(), points.end());
	std::vector<int> ans(n);
	std::vector<query_t> queries;
	auto add_query = [&](int id, int r1, int r2, int sgn) {
		if (r1 < 0 || r2 < 0) return;
		queries.emplace_back(id, r1, r2, sgn);
	};
	for (int i = 0; i < n; ++i) {
		int l1 = F.dfn[i], r1 = F.dfn[i] + F.siz[i] - 1;
		int l2 = G.dfn[i], r2 = G.dfn[i] + G.siz[i] - 1;
		add_query(i, r1, r2, 1);
		add_query(i, l1 - 1, r2, -1);
		add_query(i, r1, l2 - 1, -1);
		add_query(i, l1 - 1, l2 - 1, 1);
	}
	std::sort(queries.begin(), queries.end());
	int p = 0;
	for (auto [id, l, r, coef] : queries) {
		while (p < points.size() && points[p].first <= l) {
			tr.add(points[p].second, 1);
			++p;

		}
		ans[id] += coef * tr.query(r);
	}
	for (int i = 0; i < n; ++i) {
		std::cout << ans[i] - 1 << ' ';
	}
	std::cout << '\n';
}

詳細信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 3ms
memory: 3616kb

input:

100
63 76 68 34 53 59 51 62 82 2 90 61 40 85 46 23 34 39 73 23 36 35 61 62 53 95 72 77 17 38 44 34 82 16 18 12 53 23 50 22 1 34 95 34 31 42 10 38 17 58 4 99 68 54 31 36 11 32 54 41 42 59 68 27 60 100 11 40 39 53 83 98 50 69 98 42 74 9 95 95 25 42 87 55 90 43 55 75 14 35 60 20 6 12 22 68 13 3 51
82 5...

output:

99 13 26 0 0 0 0 0 0 0 16 0 0 0 0 0 0 69 0 0 0 0 0 0 72 0 0 0 0 0 27 0 0 0 0 42 0 46 1 27 63 0 1 0 0 1 0 0 0 15 0 0 0 0 0 0 0 3 13 1 0 0 0 0 0 0 0 10 2 0 0 0 0 1 0 0 1 0 0 0 0 74 0 0 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 

result:

ok single line: '99 13 26 0 0 0 0 0 0 0 16 0 0 ... 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 '

Test #2:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

100
21 24 30 72 42 36 85 54 26 74 63 82 96 58 78 14 76 94 97 63 75 62 50 92 21 69 86 81 38 49 6 3 42 93 88 49 67 77 23 54 26 48 49 33 29 91 80 1 55 33 16 36 36 27 54 51 22 17 93 15 32 64 18 87 1 82 44 44 19 20 71 17 33 25 5 6 91 1 95 57 23 88 3 46 64 78 4 55 25 36 48 61 85 100 16 93 16 78 19
99 72 9...

output:

99 0 0 23 35 18 0 0 0 0 0 0 0 1 32 0 0 26 29 25 0 25 13 0 21 26 90 0 16 0 0 2 0 0 0 14 0 10 0 0 0 0 0 1 0 0 0 7 89 20 0 0 0 0 0 0 36 0 0 0 0 0 33 4 0 0 10 0 0 0 35 45 0 0 39 20 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 14 2 6 2 0 53 0 0 0 

result:

ok single line: '99 0 0 23 35 18 0 0 0 0 0 0 0 ... 0 0 0 0 0 14 2 6 2 0 53 0 0 0 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

100
18 11 10 48 26 13 59 37 43 82 57 56 74 4 71 8 28 61 76 75 65 77 23 61 15 14 46 39 69 51 99 62 25 55 30 95 45 90 96 76 2 67 56 20 84 29 19 94 35 24 87 21 7 40 11 83 19 32 16 47 79 30 63 52 55 49 75 22 1 50 60 38 31 42 81 78 6 12 78 64 68 48 91 63 32 27 54 18 9 92 17 65 33 60 70 26 52 73 39
66 22 ...

output:

99 14 0 39 0 39 0 18 71 23 4 61 0 38 0 0 0 0 34 27 0 12 14 8 1 53 0 16 71 15 22 20 46 0 83 0 0 21 0 63 0 3 48 0 1 0 45 0 45 82 0 0 0 0 20 4 0 0 0 79 23 18 0 2 7 0 7 0 20 1 43 0 10 24 0 5 16 8 30 0 21 8 66 19 0 0 3 0 0 63 13 19 0 49 34 23 0 0 14 0 

result:

ok single line: '99 14 0 39 0 39 0 18 71 23 4 6...0 63 13 19 0 49 34 23 0 0 14 0 '

Test #4:

score: 0
Accepted
time: 3ms
memory: 3608kb

input:

100
78 28 42 12 10 58 15 92 71 30 64 77 66 66 45 2 21 86 88 14 65 93 25 98 79 17 53 1 95 35 91 68 13 62 83 4 49 34 29 94 2 74 57 96 72 32 84 59 61 47 3 20 55 29 87 42 57 19 70 75 99 44 78 27 40 33 73 89 11 8 76 7 26 6 82 51 90 56 5 41 23 67 40 52 97 22 37 48 15 54 50 69 36 63 31 80 60 18 85
1 42 85 ...

output:

99 43 3 0 5 3 8 3 0 1 1 8 2 4 10 0 7 1 2 2 1 2 0 0 0 1 3 1 21 6 1 6 3 1 3 2 6 0 0 54 1 10 0 7 1 0 4 0 0 0 4 1 2 5 1 4 10 10 2 0 0 5 5 4 2 43 1 0 3 2 6 1 3 1 0 0 0 10 0 3 0 1 0 8 0 3 1 4 5 0 2 1 3 2 0 1 0 2 4 0 

result:

ok single line: '99 43 3 0 5 3 8 3 0 1 1 8 2 4 ... 3 1 4 5 0 2 1 3 2 0 1 0 2 4 0 '

Test #5:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

100
12 24 61 84 11 73 71 80 48 95 68 14 67 92 70 7 37 45 15 17 23 20 36 49 53 43 59 51 21 30 63 2 100 42 86 50 35 6 38 29 47 87 39 99 1 31 25 26 22 98 60 41 40 64 10 85 74 65 28 78 16 94 5 46 79 3 91 8 56 4 93 9 82 57 13 81 18 27 88 89 76 69 44 97 90 72 33 55 34 32 58 77 66 83 52 54 19 75 96
12 24 6...

output:

99 37 85 67 56 60 31 65 33 4 61 38 82 83 76 1 30 70 14 75 29 73 74 86 6 8 46 95 11 28 27 41 36 90 24 87 71 23 59 22 10 25 47 58 15 98 26 5 7 72 12 93 9 21 54 3 18 78 96 94 68 0 42 55 97 44 84 39 64 2 66 49 32 79 17 81 51 69 45 34 52 80 63 57 19 88 48 35 53 89 40 77 50 43 62 92 20 13 16 91 

result:

ok single line: '99 37 85 67 56 60 31 65 33 4 6... 40 77 50 43 62 92 20 13 16 91 '

Test #6:

score: 0
Accepted
time: 3ms
memory: 3608kb

input:

100
45 1 69 28 44 12 93 56 14 13 46 54 18 33 65 3 35 21 7 50 64 61 95 34 2 17 31 97 94 30 91 63 8 11 40 51 74 99 92 10 20 83 78 25 87 43 77 67 66 47 80 37 72 9 16 82 76 15 96 22 29 98 58 19 86 48 26 79 6 23 53 57 85 24 5 75 100 52 70 49 90 62 32 4 38 68 89 39 27 55 41 81 60 84 42 73 71 36 88
68 1 69...

output:

99 24 98 57 11 60 20 31 45 75 79 19 79 76 0 47 97 77 49 19 49 8 6 39 29 25 96 10 90 14 14 42 2 30 77 71 84 54 69 72 74 19 84 64 28 23 85 36 34 50 84 60 83 79 44 46 93 10 0 17 7 89 3 9 48 49 35 24 58 61 4 82 92 55 36 10 36 65 59 60 31 94 88 41 55 53 24 67 68 94 43 73 31 16 40 18 91 4 70 66 

result:

ok single line: '99 24 98 57 11 60 20 31 45 75 ...4 43 73 31 16 40 18 91 4 70 66 '

Test #7:

score: 0
Accepted
time: 3ms
memory: 3680kb

input:

100
55 41 49 8 71 81 87 80 79 40 59 86 4 53 67 6 65 72 2 91 28 78 95 88 94 93 16 23 100 66 74 54 39 12 20 90 17 32 68 60 99 46 42 34 7 11 21 84 92 1 14 9 38 75 37 58 50 57 73 56 43 3 62 64 36 25 24 52 13 22 15 69 27 26 45 98 30 19 35 48 5 47 82 89 76 33 51 63 83 61 29 96 77 10 85 18 44 70 31
75 60 8...

output:

99 47 36 79 83 45 7 42 29 23 9 16 29 39 27 47 89 1 25 23 5 46 39 21 48 25 33 93 19 41 43 32 43 31 31 45 7 44 63 19 73 55 5 27 61 3 17 9 40 18 49 77 14 87 24 13 17 35 33 37 6 2 71 3 1 22 95 10 38 57 91 13 75 65 49 30 26 20 12 15 4 41 8 81 69 59 85 97 35 15 11 37 67 51 11 34 0 53 28 21 

result:

ok single line: '99 47 36 79 83 45 7 42 29 23 9...5 11 37 67 51 11 34 0 53 28 21 '

Test #8:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

1000
538 691 13 706 776 501 474 167 316 370 826 968 993 646 972 986 38 22 817 559 133 893 528 805 664 180 257 354 706 704 969 907 755 679 56 363 93 406 965 331 632 319 689 346 976 224 927 25 946 992 947 672 799 65 323 625 267 346 883 42 187 189 673 487 473 998 617 787 940 421 842 32 861 2 293 775 65...

output:

999 218 0 0 187 0 0 0 0 0 0 0 342 0 0 0 0 0 0 0 0 0 0 569 0 0 0 0 1 0 0 1 0 16 0 0 0 0 0 0 0 3 0 17 0 0 0 0 0 0 1 0 205 3 0 1 0 774 0 1 0 3 0 140 0 0 0 0 0 0 0 0 0 273 0 1 268 0 0 0 109 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 636 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 0 0 1 1 98 0 0 0 0 213 0 0 0 0 210 0 ...

result:

ok single line: '999 218 0 0 187 0 0 0 0 0 0 0 ... 1 0 0 0 778 1 0 1 0 144 2 0 0 '

Test #9:

score: 0
Accepted
time: 4ms
memory: 3880kb

input:

1000
662 971 277 239 95 391 237 894 639 664 548 777 202 670 300 112 614 618 973 161 212 610 384 602 124 543 26 5 448 882 595 526 931 45 216 608 86 390 473 465 870 965 876 695 426 909 398 268 88 397 822 809 889 138 119 607 548 546 367 707 449 610 515 400 302 732 290 255 334 654 957 317 596 373 541 94...

output:

999 66 0 0 8 430 797 80 46 0 0 0 0 0 207 0 0 1 0 83 0 0 7 344 0 0 0 0 1 0 0 0 320 103 334 0 90 0 138 0 0 0 105 0 0 1 328 0 0 0 0 0 1 161 0 0 103 528 0 0 172 0 0 0 0 0 0 330 0 0 55 93 0 11 92 60 230 507 0 222 0 203 192 0 0 525 0 378 0 0 23 0 0 2 283 0 0 0 348 1 0 0 0 0 0 0 423 274 0 199 0 189 0 0 0 0...

result:

ok single line: '999 66 0 0 8 430 797 80 46 0 0...0 0 177 0 259 113 0 0 352 60 0 '

Test #10:

score: 0
Accepted
time: 4ms
memory: 3844kb

input:

1000
946 897 577 400 440 68 146 639 974 291 655 907 963 747 225 201 522 419 890 971 593 501 168 551 15 724 575 931 546 163 10 644 562 651 373 156 250 187 126 13 915 142 376 672 437 743 581 186 960 608 388 1000 538 811 80 718 980 255 571 460 905 489 41 321 390 989 485 177 484 600 934 717 661 338 271 ...

output:

999 19 107 412 173 240 0 0 555 6 260 65 290 739 771 33 101 100 508 0 0 0 143 17 103 91 27 2 0 0 0 109 161 70 81 16 0 751 0 0 234 0 143 180 91 155 0 25 0 0 0 319 0 484 0 430 98 82 71 665 614 4 353 0 123 0 157 1 45 0 0 0 352 304 1 0 57 0 0 0 0 0 0 0 467 0 4 251 10 68 0 0 35 266 1 63 0 139 102 0 154 12...

result:

ok single line: '999 19 107 412 173 240 0 0 555...684 0 205 255 108 0 133 480 59 '

Test #11:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

1000
60 619 838 186 660 782 519 907 452 730 27 292 913 885 434 565 660 275 653 286 935 62 715 546 562 759 64 897 287 964 799 646 349 852 737 285 945 569 571 311 872 46 205 35 687 75 825 388 23 531 509 703 210 835 407 800 252 486 52 853 361 982 406 573 816 374 1000 222 29 305 641 277 342 365 412 267 ...

output:

999 24 20 17 14 159 8 1 0 1 159 6 8 9 0 4 4 3 1 10 2 19 4 7 1 12 19 3 2 8 14 18 10 4 13 1 2 15 3 6 14 8 2 8 13 21 10 0 15 0 1 8 6 1 0 3 3 1 12 5 95 7 6 7 3 0 4 14 1 0 4 9 6 7 13 20 0 17 29 24 7 14 0 0 9 6 5 6 10 19 15 2 11 2 3 8 7 22 14 0 9 1 4 24 0 4 1 3 12 20 23 9 5 2 22 15 2 21 1 5 16 15 7 0 9 0 ...

result:

ok single line: '999 24 20 17 14 159 8 1 0 1 15... 15 1 8 11 0 4 5 0 6 0 15 2 19 '

Test #12:

score: 0
Accepted
time: 3ms
memory: 3876kb

input:

1000
948 74 204 137 931 770 960 369 963 450 597 882 179 838 171 986 776 966 391 208 535 579 477 193 855 795 959 642 162 223 726 518 769 727 955 888 779 527 667 112 475 139 661 128 894 716 539 345 817 399 704 629 575 994 96 257 64 85 914 901 377 737 234 312 243 540 386 203 739 384 237 297 799 483 301...

output:

999 21 915 5 315 263 381 575 592 498 437 87 598 47 429 72 831 260 860 254 385 81 538 780 822 502 664 214 158 829 519 654 904 171 135 794 295 156 431 558 425 280 985 343 305 256 946 226 451 741 672 604 895 941 454 752 154 901 755 544 819 610 848 902 582 481 109 719 120 354 617 100 210 916 489 621 835...

result:

ok single line: '999 21 915 5 315 263 381 575 5...561 455 975 847 113 52 964 229 '

Test #13:

score: 0
Accepted
time: 4ms
memory: 3936kb

input:

1000
295 318 366 368 178 652 246 531 861 943 937 430 591 198 225 822 376 870 999 101 880 475 896 467 487 792 133 168 128 966 758 208 113 913 471 553 731 538 709 454 348 738 422 933 756 717 599 382 338 791 134 98 906 774 233 772 119 162 724 863 536 228 783 357 633 110 897 355 619 558 439 9 481 97 33 ...

output:

999 680 610 797 151 931 771 457 707 95 600 433 470 105 277 475 550 186 995 100 910 843 405 867 274 352 139 260 121 756 841 613 227 490 451 769 576 436 788 105 965 955 423 805 555 37 500 90 652 585 925 31 758 961 481 799 526 951 468 389 724 973 0 149 74 470 234 130 71 306 929 846 706 966 979 226 249 ...

result:

ok single line: '999 680 610 797 151 931 771 45...775 171 876 805 529 50 101 753 '

Test #14:

score: 0
Accepted
time: 4ms
memory: 3864kb

input:

1000
172 777 442 83 703 373 853 131 894 478 831 377 324 586 283 62 781 741 621 477 176 951 108 65 634 455 408 984 992 169 332 114 316 816 679 636 49 37 843 208 341 434 27 4 436 558 897 595 709 228 44 433 505 302 771 559 770 223 833 404 611 30 553 441 216 410 233 464 22 898 421 428 516 71 910 386 525...

output:

999 805 365 509 165 347 202 231 282 442 907 179 929 258 498 294 81 477 54 991 351 489 223 490 627 775 767 445 249 711 214 707 537 370 453 693 450 114 899 143 212 69 891 383 254 281 557 203 229 457 763 765 5 79 22 389 358 987 65 147 849 41 355 139 314 129 172 155 599 244 503 487 53 470 251 171 171 28...

result:

ok single line: '999 805 365 509 165 347 202 23...93 323 893 140 933 709 407 276 '

Test #15:

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

input:

2000
1889 820 922 249 1445 1857 119 1763 1699 302 756 278 1827 45 1786 955 1233 942 923 1603 1881 112 366 499 795 1225 1475 1328 397 171 1905 99 614 1355 633 517 1905 14 1563 431 1456 1778 776 847 1762 757 958 1648 330 595 980 1321 301 1244 689 1130 46 314 17 1748 710 51 1554 225 449 1626 1112 823 1...

output:

1999 133 2 120 408 0 0 0 1 1 0 148 0 0 0 1 483 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 407 1264 0 0 0 0 1 0 0 0 348 1 0 0 0 0 0 0 0 0 0 0 897 0 0 0 0 0 0 378 1 0 84 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 289 0 362 2 0 1 0 0 0 0 688 0 0 0 0 0 292 0 0 0 20 0 0 482 0 0 0 0 0 0 0 0 1023...

result:

ok single line: '1999 133 2 120 408 0 0 0 1 1 0... 0 0 0 0 0 0 0 4 0 0 691 0 0 0 '

Test #16:

score: 0
Accepted
time: 2ms
memory: 4056kb

input:

2000
174 1511 612 1466 1130 657 1800 1646 1592 1908 1604 840 1366 716 1493 69 1412 1083 710 1225 1229 1156 269 1443 1804 1080 71 25 531 1307 1562 1441 597 121 291 411 1684 1837 1733 1287 152 346 1176 1695 1197 1026 1940 1674 965 1536 114 203 1577 606 1995 194 590 362 61 389 1289 226 78 1178 782 1433...

output:

1999 270 0 0 96 362 16 0 6 900 102 0 0 1 0 0 1 0 1 0 0 1 347 466 751 0 214 0 288 0 0 1 0 0 0 0 0 354 2 0 179 0 902 0 816 0 0 1060 1647 0 1124 0 0 0 429 1 0 2 0 0 0 1129 0 0 0 0 0 0 1374 0 0 0 0 0 39 0 0 31 0 0 0 0 211 0 0 0 0 611 1001 0 0 0 0 363 93 0 0 0 0 1110 394 0 0 0 2 1787 0 1 745 0 978 1172 0...

result:

ok single line: '1999 270 0 0 96 362 16 0 6 900... 0 801 1 0 614 170 0 0 3 0 0 1 '

Test #17:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

2000
1321 980 867 1028 1936 1577 1143 715 1739 1450 1625 51 541 1590 781 1186 1682 1026 1611 368 890 1819 1675 1849 246 1749 912 1300 1157 534 1684 1455 1519 1284 1072 1308 1448 1160 312 1977 1366 1524 1743 487 1010 1520 352 1441 1963 1955 355 1152 317 1841 1747 1241 811 1862 509 789 87 950 30 40 12...

output:

1999 411 0 0 237 0 0 0 560 1176 80 0 366 0 0 179 75 218 247 195 31 0 0 0 0 286 1421 0 425 561 509 0 0 1517 417 0 405 0 0 248 0 30 9 0 1600 246 565 66 1202 0 1 1 0 0 0 166 949 1304 6 351 127 1881 1515 524 422 0 521 0 203 425 0 331 997 273 0 0 0 1275 74 1 226 49 973 32 0 243 303 466 0 56 0 0 0 647 248...

result:

ok single line: '1999 411 0 0 237 0 0 0 560 117...3 101 0 17 26 88 0 575 1 455 0 '

Test #18:

score: 0
Accepted
time: 4ms
memory: 4120kb

input:

2000
1082 901 1235 1912 29 1475 1782 1490 593 1258 662 675 1141 8 791 1481 218 1535 1137 276 520 1734 1644 1139 864 366 1121 1078 1613 18 116 21 1284 83 138 807 1483 1837 1597 1670 490 512 717 1215 76 1823 368 1333 1270 1818 1387 783 523 7 1220 1439 1496 502 1666 1614 516 1048 1030 537 1639 1478 329...

output:

1999 21 0 8 3 8 2 7 2 4 9 20 7 37 11 10 4 0 20 14 2 21 13 0 5 27 25 6 8 5 17 20 4 1 11 6 9 7 3 1 24 0 1 26 6 0 4 16 39 3 0 12 21 1 6 9 0 6 6 0 9 6 17 19 1 5 0 1 24 17 22 44 14 5 22 9 16 6 1 15 3 5 10 0 3 0 6 6 6 14 0 1 6 7 19 14 3 0 3 6 7 2 2 33 13 10 0 33 23 26 4 16 3 6 8 18 17 29 15 11 3 12 7 8 1 ...

result:

ok single line: '1999 21 0 8 3 8 2 7 2 4 9 20 7...5 18 11 9 15 8 4 38 15 40 15 4 '

Test #19:

score: 0
Accepted
time: 4ms
memory: 4028kb

input:

2000
1013 1665 1883 77 1085 1907 778 1268 701 119 619 1846 1117 1651 1235 1657 988 91 1855 1711 816 1327 1929 1792 348 1322 1107 390 1774 1523 1246 1034 1044 1725 1608 301 1254 523 159 1597 328 725 1242 813 114 1155 703 1818 1291 241 1062 158 675 1157 867 446 364 14 333 789 757 1153 1436 1706 317 33...

output:

1999 123 1845 255 1741 314 1961 1379 826 1372 1544 1016 818 1644 397 280 1108 1177 1130 1685 725 1853 773 119 1675 863 1766 697 38 1611 417 70 1573 1802 452 1885 1799 272 645 1064 1450 1782 225 1474 1426 194 347 802 1268 240 899 1433 1258 360 1271 1699 1206 1600 1643 385 1903 893 1883 1295 529 1897 ...

result:

ok single line: '1999 123 1845 255 1741 314 196...09 1429 1456 478 1273 1873 845 '

Test #20:

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

input:

2000
1879 161 464 1025 1763 1477 1027 855 1156 1963 1387 1188 447 418 1562 427 590 572 493 217 1140 68 1238 367 1964 1575 483 479 491 1187 1773 834 78 1986 756 1236 1647 106 142 276 502 545 175 584 438 609 1769 1397 186 393 1391 771 514 765 1889 1199 1863 1138 1051 1101 1431 1854 240 1165 1571 1559 ...

output:

1999 674 1984 574 239 1324 1232 1339 1661 1715 170 570 914 214 859 1025 13 211 1844 307 1516 1699 1755 864 623 1344 142 775 1578 606 894 1217 520 1505 870 836 175 1789 975 1083 1356 1324 541 1253 1826 429 578 686 967 1540 480 89 1334 607 656 1189 428 85 381 785 1509 1105 694 1302 1435 402 327 1754 1...

result:

ok single line: '1999 674 1984 574 239 1324 123...7 1860 31 933 188 447 1144 243 '

Test #21:

score: 0
Accepted
time: 4ms
memory: 3980kb

input:

2000
827 154 1285 1324 812 535 1887 1475 1405 108 1815 629 15 1201 1454 1941 512 1881 1193 846 644 1084 589 329 147 1215 1570 727 1833 1125 805 505 1586 1053 1590 236 1466 457 1908 1170 1910 1283 1769 1492 1744 1373 770 1244 461 1096 756 1189 173 585 1372 503 1295 1335 1036 1191 133 342 1250 1645 54...

output:

1999 33 347 444 76 1553 1987 81 667 1457 453 591 543 161 323 1253 1325 1301 190 614 1517 1609 513 1275 1621 1595 499 276 237 558 317 1791 181 596 1491 726 35 205 1413 689 1357 1323 1351 457 615 1965 31 1823 1075 217 616 1795 1389 607 307 966 900 405 579 295 1617 536 1839 1303 829 1383 975 297 1709 5...

result:

ok single line: '1999 33 347 444 76 1553 1987 8... 1177 209 303 820 1953 570 546 '

Subtask #2:

score: 70
Accepted

Dependency #1:

100%
Accepted

Test #22:

score: 70
Accepted
time: 102ms
memory: 26108kb

input:

100000
89001 63109 50334 40606 1995 11002 52081 91388 69370 61105 40871 54691 72083 56944 95551 50027 36748 34897 31961 83065 64555 38885 56122 4762 49461 54824 1669 70753 83357 33050 69230 21611 63378 67657 89079 71574 15131 22786 68684 10235 69512 11978 74561 27830 46049 18707 66744 89840 74449 89...

output:

99999 1 32960 0 1 0 0 0 0 0 0 0 0 0 73809 3952 1 0 0 14179 0 0 0 1 0 0 0 0 10158 0 2 0 0 0 0 21692 0 0 0 62756 0 9210 1208 0 0 0 21792 0 0 0 114 22313 0 0 0 0 49171 0 0 0 0 0 1 1 0 0 0 36648 0 2621 0 40743 0 0 49529 0 0 0 0 2 0 0 0 0 0 0 38915 7296 0 0 0 0 0 0 0 0 0 0 1424 1 0 30036 0 0 1 0 66113 0 ...

result:

ok single line: '99999 1 32960 0 1 0 0 0 0 0 0 ...82 0 0 0 0 0 0 0 0 5 1 0 0 2 1 '

Test #23:

score: 0
Accepted
time: 108ms
memory: 26304kb

input:

100000
10080 46797 25117 41372 2299 65794 57514 82572 52540 41360 92644 35462 20230 52206 40696 81386 99118 3731 53520 59670 94432 80953 91346 54800 35919 52472 41043 34366 35886 53410 12006 11899 3694 71659 31911 81292 57696 18742 85596 48873 36090 64877 66609 61840 54684 45490 59274 33245 14213 29...

output:

99999 0 0 0 0 1634 0 26 0 3353 1 0 29954 17023 0 34374 0 2059 0 0 0 0 19905 0 13115 0 69109 0 48226 7933 31929 93951 0 0 0 3617 0 60908 0 60200 28312 0 0 0 0 22512 0 1257 1316 13707 2550 16846 0 0 44510 0 0 0 18713 0 938 0 36724 0 0 0 0 0 34995 0 0 0 0 0 61535 69165 0 12402 0 0 59344 40454 23744 235...

result:

ok single line: '99999 0 0 0 0 1634 0 26 0 3353...1 0 49908 0 0 60560 3429 0 0 0 '

Test #24:

score: 0
Accepted
time: 107ms
memory: 29132kb

input:

100000
3784 2321 82038 26098 84432 90771 68854 11907 42506 71773 71853 12180 33344 94020 65661 29775 7284 98832 13766 45361 98126 28390 46902 13046 19272 67398 5090 99384 6798 4418 4376 22462 96029 9034 21474 49359 83674 90582 40815 41483 17145 14114 4779 20547 39742 51414 47941 34386 15250 35109 49...

output:

99999 70266 0 22536 11152 0 62771 37823 29951 54659 0 0 0 37185 0 3206 3169 0 35672 0 26461 0 0 7806 11382 9447 25496 22114 0 56586 0 20938 0 0 0 2367 87398 24761 0 2549 0 5084 1156 18870 0 29869 0 37311 0 1 0 0 0 4336 1030 63202 22481 5253 21377 0 7908 0 35566 2147 20454 732 41980 1972 0 0 4027 0 0...

result:

ok single line: '99999 70266 0 22536 11152 0 62... 0 0 26623 0 0 28562 0 0 0 810 '

Test #25:

score: 0
Accepted
time: 97ms
memory: 26764kb

input:

100000
67234 76416 67028 21289 33669 62511 23542 27801 93424 59172 93823 40849 91778 37927 15421 34883 22122 62073 34450 1058 40607 70557 65408 4234 33370 47269 71112 23617 23752 32740 12475 55718 96644 41144 22625 5445 56246 90507 12112 44122 36741 32630 55749 57378 51446 46383 22498 79121 76690 22...

output:

99999 9 63 42 197 62 31 16 20 4 267 12 129 19 50 52 7 7 33 3 38 5 111 25 16 136 1 86 26 59 65 59 6 60 84 261 36 35 22 50 10 57 186 17 1 117 16 42 127 44 22 278 56 158 175 24 14 86 107 201 57 96 36 27 7 126 38 3 31 5 108 204 6 12 6 26 83 33 52 71 247 56 38 15 2 124 19 9 19 21 35 31 70 44 54 103 22 80...

result:

ok single line: '99999 9 63 42 197 62 31 16 20 ... 124 162 125 21 116 23 4 19 96 '

Test #26:

score: 0
Accepted
time: 103ms
memory: 30140kb

input:

100000
45471 10381 52753 45696 37866 67914 30142 92457 37867 45614 58059 17271 61325 68518 71876 94611 2232 49869 18618 70957 68009 7395 99677 70923 17519 91546 48774 22511 53762 26281 44808 14018 98958 52349 34654 57085 77424 26659 79858 22942 76522 75828 25424 48113 81457 60764 98785 10648 59931 4...

output:

99999 40247 64807 84814 79500 8967 67116 85511 42384 41983 10584 90992 70857 66377 71644 37528 34150 86189 68511 59952 14704 86763 64584 64680 80579 25014 97097 64839 38903 13949 64296 24915 95305 62254 90544 21873 77702 46338 54986 19521 16355 9004 94967 61900 50454 99773 15119 29629 41078 68092 52...

result:

ok single line: '99999 40247 64807 84814 79500 ...92 646 83810 77169 32506 92346 '

Test #27:

score: 0
Accepted
time: 97ms
memory: 29720kb

input:

100000
21196 82626 73990 9792 28463 63464 74991 84774 31591 69558 94952 64947 31797 84477 62058 65489 81309 84425 27181 22101 23371 17099 36723 465 96623 98932 27071 32849 24412 16694 46326 806 66071 9697 52866 41415 63840 51044 1355 67741 99828 43566 35884 46 51636 37959 9915 46720 22961 82690 4812...

output:

99999 93984 5498 2186 41271 24861 20608 10841 80996 95848 67832 27754 13899 93819 46990 30664 32391 80627 11116 67629 4275 6051 83379 11653 81825 18232 77289 83666 69581 35207 23324 1186 46585 68820 97040 23640 36904 13986 32523 36984 65380 36861 44262 73860 78585 78586 83434 38453 69791 21956 37760...

result:

ok single line: '99999 93984 5498 2186 41271 24...56 93638 734 21486 41276 50714 '

Test #28:

score: 0
Accepted
time: 108ms
memory: 29864kb

input:

100000
34065 77269 77528 81271 55816 76078 50995 25768 90496 26488 18093 46138 36966 72247 90975 50986 11737 2894 51529 39955 35201 63183 74872 17926 43772 85585 63794 78660 90638 70422 45889 24263 7570 14215 25065 57700 92815 18521 33859 61755 43756 4435 23332 42511 82430 79407 55109 76149 62396 71...

output:

99999 2016 46577 92791 43720 19006 36389 46775 77923 60455 27797 24246 15059 11710 9379 45013 79813 21744 41272 7925 41213 15828 94677 75533 8957 63893 17847 16345 62829 30123 25530 28677 81269 22463 8911 39415 29931 41589 30794 46225 49685 14806 17937 73729 22523 55877 79551 2936 30887 5119 29415 2...

result:

ok single line: '99999 2016 46577 92791 43720 1...6 36577 23509 36923 8955 18495 '

Test #29:

score: 0
Accepted
time: 247ms
memory: 44276kb

input:

190000
69514 150948 76737 37178 52086 42771 151880 111835 187731 72547 162385 43726 172619 64047 126067 92919 136835 176979 15464 156706 81622 19659 71257 10995 145023 36528 91861 41049 105528 33639 105698 62469 140 136971 166556 53347 86754 9093 30303 185620 52779 184732 172785 15276 40507 74702 13...

output:

189999 1 0 0 0 0 0 0 0 4 5989 9927 0 0 0 0 12428 0 22827 55425 0 0 0 2 0 0 0 0 1 0 26063 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 54475 1 0 0 0 0 0 0 0 0 0 0 1 0 125992 3 0 0 84277 0 0 0 0 0 2 0 0 0 35723 1 0 0 0 0 0 0 0 0 0 0 4 0 0 123359 0 0 1 1215 0 0 150637 0 0 2 0 1 0 0 74897...

result:

ok single line: '189999 1 0 0 0 0 0 0 0 4 5989 ...8451 0 0 74347 0 0 0 0 0 0 0 1 '

Test #30:

score: 0
Accepted
time: 235ms
memory: 46576kb

input:

190000
180683 58192 167984 131745 102609 32042 146469 161302 43307 84383 89568 91144 70127 134400 74410 24447 59021 147083 164245 149604 128170 23153 181924 43080 34686 146028 72133 44405 172078 98114 122408 94424 26035 54474 56679 133494 164955 74428 162270 90665 16530 121066 124806 55496 83651 363...

output:

189999 1173 0 27385 0 0 0 0 0 1 74272 0 0 0 0 44263 0 59995 0 152256 0 0 0 5379 0 56918 0 59168 0 148498 0 12737 0 0 2420 27904 1 1 0 62976 0 0 62981 25779 0 0 0 48045 0 0 0 5026 73951 0 0 39084 52528 85914 0 0 4510 0 0 0 34622 0 0 0 49945 47421 69186 0 0 1 2 0 3161 64998 1233 0 2 0 85165 0 0 96280 ...

result:

ok single line: '189999 1173 0 27385 0 0 0 0 0 ...628 0 91915 0 1963 114635 4883 '

Test #31:

score: 0
Accepted
time: 253ms
memory: 49700kb

input:

190000
173979 166989 112560 65949 8839 19201 147624 180515 96962 109062 181139 110490 38234 8528 43632 177774 89954 80415 12489 146116 101057 141269 89633 89715 140380 111125 185615 40655 38533 59480 128169 168897 156209 85487 151097 10598 133238 86504 62906 121695 7298 55848 144675 40256 127442 940...

output:

189999 11366 117124 68872 0 8086 11315 39644 0 0 126470 14863 4007 43684 0 77718 14621 21076 0 17559 33768 0 126845 15485 0 31477 59766 6797 0 3559 112948 59543 0 11407 0 0 0 0 38777 29607 0 16940 19177 0 0 67382 0 3385 21293 24587 0 0 10029 97065 100015 0 32965 0 50719 38074 2546 13017 0 0 0 101787...

result:

ok single line: '189999 11366 117124 68872 0 80...1162 56779 0 20281 25294 0 0 0 '

Test #32:

score: 0
Accepted
time: 265ms
memory: 46660kb

input:

190000
146419 80971 16574 13475 166589 80553 8803 13678 60601 18376 144641 38456 185451 189082 106127 176086 69431 160424 64181 163288 68718 116694 50426 82451 60438 51254 114030 71299 74148 6863 111869 128328 118933 28582 73463 155467 91364 1563 32204 122142 69127 170458 131901 183009 73824 146657 ...

output:

189999 19 151 17 53 145 243 245 129 277 111 108 39 11 199 285 34 39 29 75 8 237 10 74 126 53 403 214 33 21 63 7 190 281 115 348 125 75 273 17 81 44 52 266 48 49 150 25 74 16 146 85 141 83 64 120 34 20 70 364 55 80 29 153 54 54 3 42 45 326 116 96 142 94 251 56 252 8 11 330 37 72 29 203 48 6 103 237 5...

result:

ok single line: '189999 19 151 17 53 145 243 24...9 206 22 34 137 370 322 345 92 '

Test #33:

score: 0
Accepted
time: 249ms
memory: 53236kb

input:

190000
106852 174445 92119 182470 106325 158092 8102 185060 122298 140821 63100 32943 7772 189358 27879 74262 80632 71749 47386 129488 130992 130676 83124 167773 161123 110613 156676 138172 12106 20388 180363 93137 23448 89457 58125 43488 25196 168965 31639 52629 140932 31465 32801 48563 109170 8411...

output:

189999 33491 20225 161104 129868 39275 110099 150643 114173 51730 159103 105738 89218 70052 3638 109324 168946 175827 10894 125619 104927 159416 78754 178115 170126 50642 151965 18598 28222 90095 141486 110096 183713 52715 183956 97329 130463 132543 86878 74019 35693 55140 175566 92175 121919 76050 ...

result:

ok single line: '189999 33491 20225 161104 1298...6355 41827 109451 83704 169888 '

Test #34:

score: 0
Accepted
time: 238ms
memory: 53228kb

input:

190000
142925 20851 13346 20575 82265 126947 2340 109292 104264 183045 3221 24372 107797 113271 76426 151102 125065 121005 187290 124463 6076 32805 76012 61452 76424 49625 4330 94144 62607 19102 132071 133628 182017 169359 137726 126270 111098 92422 23528 47817 95684 186633 151569 3546 51523 116210 ...

output:

189999 183812 149726 180710 80078 172809 18360 158733 183491 102954 159276 150884 29820 187535 75350 184750 22580 50757 108505 179666 163056 420 2201 3085 64324 53859 144324 60326 125620 104187 177152 127813 27422 86314 82919 158724 161397 186939 131424 125124 126224 30630 63654 189375 99600 126946 ...

result:

ok single line: '189999 183812 149726 180710 80...31567 101794 17764 14499 53728 '

Test #35:

score: 0
Accepted
time: 243ms
memory: 53048kb

input:

190000
112026 188452 185293 110010 24145 113648 108045 128638 117243 148401 106834 132076 150467 187471 35532 179899 26761 57783 107621 72031 66282 77795 141446 13848 64011 32795 2946 134922 51038 178731 33270 35533 96523 116368 67404 95329 76888 147840 67180 159780 4708 64403 11488 30955 54850 8878...

output:

189999 13098 41097 99637 39892 113373 17303 70409 80142 108421 43433 32905 28545 86976 135795 141735 94911 68031 5325 166381 13575 34867 15826 37663 3707 5323 54744 94399 25765 6989 182533 177819 37675 163131 94567 154391 5875 6505 165657 167477 164855 40335 58285 30740 110875 16898 76559 128899 580...

result:

ok single line: '189999 13098 41097 99637 39892...47861 76336 27645 166549 15291 '

Test #36:

score: 0
Accepted
time: 267ms
memory: 45436kb

input:

200000
180895 44756 25499 195516 88865 73796 136938 178982 53968 154562 143043 57344 151417 146421 28583 169082 20872 70585 65726 79949 114151 154826 7743 156876 5854 109919 28644 148609 66265 118006 42085 129065 36802 183968 154711 21034 140192 75173 161091 35222 493 108989 81854 153694 2136 165462...

output:

199999 3 2 0 3 0 0 0 2 0 0 120414 0 0 0 21787 66510 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 10778 0 68074 0 0 1 0 187034 0 0 44159 30632 0 36472 47979 0 0 11692 0 11932 0 0 18025 0 0 0 0 0 4382 0 0 0 42235 0 0 1 0 0 0 0 0 16234 0 0 29088 1 0 4135 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 136136 84136 1 0 0 15091 0 ...

result:

ok single line: '199999 3 2 0 3 0 0 0 2 0 0 120... 83477 52314 0 0 0 82987 79545 '

Test #37:

score: 0
Accepted
time: 272ms
memory: 48096kb

input:

200000
35186 62374 141488 199227 21112 40668 50480 149219 101245 27866 74353 147412 54831 65090 90082 178568 77547 99411 115457 87785 47418 73763 182032 126942 113199 765 10005 163061 176469 34556 4152 160413 3768 23671 51938 50663 18847 196976 10081 18924 25271 95360 167481 163933 98183 177910 1671...

output:

199999 0 69045 0 4744 0 49977 0 0 0 57620 5864 78597 0 0 0 14953 50612 0 45534 0 116836 0 0 0 99631 1 65523 0 0 81085 0 0 0 0 0 0 118028 15927 0 0 0 40506 0 78758 90156 37758 0 0 0 0 1 9293 0 0 0 82287 0 97939 0 0 0 0 1 76432 100910 0 0 1 0 0 0 0 0 0 0 0 0 70291 1 0 6477 0 78015 0 38102 0 2 0 0 0 0 ...

result:

ok single line: '199999 0 69045 0 4744 0 49977 ...0 0 0 0 0 0 77040 0 2886 0 0 0 '

Test #38:

score: 0
Accepted
time: 261ms
memory: 51128kb

input:

200000
4420 21750 28088 39324 55463 16003 25387 60507 153458 63961 66080 43250 43161 27269 5881 80765 136184 81106 126803 108619 93173 6070 57771 196258 165671 34479 22943 71419 34993 144951 20962 125851 103473 29601 26034 189773 24901 158449 88067 74544 8609 25873 198351 156162 82289 157637 27837 8...

output:

199999 0 70574 0 7661 63823 0 29504 111650 7646 41271 5689 16867 43709 0 0 1990 0 5434 0 73983 0 102 112658 0 0 80609 137905 3294 0 114654 0 0 19683 118479 0 0 43200 0 38042 64649 80539 6123 93155 15888 0 20713 92767 87653 0 74542 0 0 0 54809 69889 92521 22170 56311 153163 80244 0 24579 11488 81326 ...

result:

ok single line: '199999 0 70574 0 7661 63823 0 ... 0 83783 57125 0 61089 23816 0 '

Test #39:

score: 0
Accepted
time: 255ms
memory: 47828kb

input:

200000
67983 141169 9646 106815 22654 198306 109307 171573 3832 3096 172662 168393 147321 172998 180170 6872 115901 128472 154344 46477 84685 71190 163702 83266 136749 148728 105397 14608 105435 126918 1617 69551 45177 32030 112481 169883 23440 66212 134120 120531 43546 35891 146627 159201 179347 79...

output:

199999 117 179 9 25 73 89 236 2 169 0 11 299 155 51 14 130 52 89 88 80 57 12 37 192 29119 0 50 221 81 23 6 77 117 0 28 117 178 1 156 63 130 304 281 241 391 22 43 12 96 157 51 214 166 9 42 99 378 3 150 48 18 51 66 119 27 60 69 283 59 119 129 191 64 123 12 0 26 129 37 304 102 5 139 27 35 49 12 9 61 23...

result:

ok single line: '199999 117 179 9 25 73 89 236 ... 23 48 37 40 254 70 0 82 91 15 '

Test #40:

score: 0
Accepted
time: 275ms
memory: 54968kb

input:

200000
67140 12409 119094 171722 127546 55758 123002 151561 165727 76941 199428 18411 196513 52318 127938 169735 57100 115841 192274 138414 180670 50835 169370 129363 57353 146143 108738 72605 125010 185931 135798 199678 126026 93823 170624 144043 198645 20354 48654 107963 125001 119497 34515 118240...

output:

199999 107757 87254 76897 38103 16350 115177 178193 161111 111958 56603 80032 109005 57665 106323 180574 153481 4116 103391 97610 67748 71385 137007 190802 21280 95615 113307 35267 153739 90944 122551 188542 144998 12229 111589 115981 171768 105694 163554 92905 30286 9989 85841 49269 132444 144294 2...

result:

ok single line: '199999 107757 87254 76897 3810...993 149121 42607 120938 178761 '

Test #41:

score: 0
Accepted
time: 260ms
memory: 54952kb

input:

200000
19776 59977 72240 67085 36337 128821 1392 108221 94320 157040 21359 115014 102345 174212 80479 51372 134103 145134 197507 33971 34296 25022 58211 26627 181989 79015 127332 51825 55213 65313 11879 39107 115702 21562 116816 83967 110209 70124 34294 38442 25574 14685 47930 81673 75625 6311 24476...

output:

199999 176268 35742 191608 109745 25064 198293 114938 79554 176670 188366 175245 77797 97667 63430 17084 128019 27045 50164 63765 19294 37724 3371 120041 77665 181730 133844 128522 152460 95491 133791 34245 50139 13705 168654 35253 94439 7310 17414 119410 299 145871 5224 171909 170709 189195 27734 1...

result:

ok single line: '199999 176268 35742 191608 109...49 164757 108625 143371 199229 '

Test #42:

score: 0
Accepted
time: 256ms
memory: 54852kb

input:

200000
5865 131271 43031 27506 137731 93046 9224 129394 87886 124724 160597 73602 165270 131151 102121 1320 128575 34272 69059 173779 27330 87031 87643 112257 101657 102727 102318 142757 170653 75686 193735 60790 101374 196756 81911 159927 8768 83880 111473 100861 52399 6266 12450 85033 38687 135168...

output:

199999 67745 22475 40891 69457 152451 69557 74625 67897 34651 83669 106963 88905 144459 120945 117001 199059 43570 21378 139021 150669 32956 199907 27153 20318 19593 134109 67998 65322 139469 98259 179237 93823 76292 51473 172769 46154 75757 94053 23338 167871 8391 87577 48793 140781 78751 124459 49...

result:

ok single line: '199999 67745 22475 40891 69457...27151 74443 108749 52223 96166 '

Extra Test:

score: 0
Extra Test Passed