QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319348 | #4829. Mark on a Graph | duongnc000 | 0 | 2ms | 4360kb | C++20 | 5.9kb | 2024-02-02 14:45:44 | 2024-02-02 14:45:45 |
answer
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;
// https://i11www.iti.kit.edu/extra/publications/sw-fclt-05_t.pdf
// O(n + m * sqrt(m)) process() calls for graphs without loop or multiedges
void find_3_cycles(int n, const vector<array<int, 2>> &edge, auto process){
int m = (int)edge.size();
vector<int> deg(n), order, pos(n);
vector<vector<int>> appear(m + 1), adj(n), found(n);
for(auto [u, v]: edge) ++ deg[u], ++ deg[v];
for(auto u = 0; u < n; ++ u) appear[deg[u]].push_back(u);
for(auto d = m; d >= 0; -- d) order.insert(order.end(), appear[d].begin(), appear[d].end());
for(auto i = 0; i < n; ++ i) pos[order[i]] = i;
for(auto i = 0; i < m; ++ i){
int u = pos[edge[i][0]], v = pos[edge[i][1]];
adj[u].push_back(v), adj[v].push_back(u);
}
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v){
for(auto i = 0, j = 0; i < (int)found[u].size() && j < (int)found[v].size(); ){
if(found[u][i] == found[v][j]){
process(order[u], order[v], order[found[u][i]]);
++ i, ++ j;
}
else if(found[u][i] < found[v][j]) ++ i;
else ++ j;
}
found[v].push_back(u);
}
}
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _classes;
vector<int> p;
disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
int make_set(){
p.push_back(-1);
++ _classes;
return n ++;
}
int classes() const{
return _classes;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
act(u, v, swapped);
return true;
}
void clear(){
_classes = n;
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
int n, m;
vector<array<int, 2>> G;
map<int, int> adj[1005];
int indeg[1005], av[1005];
void add_edge(int u, int v) {
++indeg[u], ++indeg[v];
adj[u][v]++, adj[v][u]++;
}
bool check(vector<int> &pos) {
for (int i = 0; i < isz(pos); ++i) {
for (int j = i + 1; j < isz(pos); ++j) {
if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
return true;
}
}
return false;
}
void solve() {
cin >> n >> m;
disjoint_set dsu(n);
iota(av + 1, av + n + 1, 1);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
// dsu.merge(u, v);
// G.push_back({u, v});
}
sort(av + 1, av + n + 1, [&](int x, int y) {
return indeg[x] > indeg[y];
});
int cnt = 0;
vector<int> pos;
vector<pair<int, int>> op;
for (int i = 1; i <= 10; ++i) if (indeg[av[i]] % 2) {
pos.emplace_back(av[i]);
}
while (isz(pos) > 1 and check(pos)) {
int woo1 = -1, woo2 = -1;
for (int i = 0; i < isz(pos); ++i)
for (int j = i + 1; j < isz(pos); ++j)
if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
woo1 = i, woo2 = j;
add_edge(pos[woo1], pos[woo2]);
op.emplace_back(pos[woo1], pos[woo2]);
vector<int> npos;
for (int i = 0; i < isz(pos); ++i) if (i != woo1 and i != woo2) npos.emplace_back(pos[i]);
pos = npos;
}
for (int idx : pos) {
for (int j = n; j >= 1; --j) if (adj[idx].find(av[j]) == adj[idx].end()) {
add_edge(av[j], idx);
op.emplace_back(av[j], idx);
break;
}
}
if (isz(op) == 0) {
cout << "ok" << endl;
return;
}
cout << "mark" << endl << isz(op) << endl;
for (auto [u, v] : op) cout << u << " " << v << endl;
// for (int i = 0; i < 10; ++i) cout << indeg[av[i + 1]] << " \n"[i == 9];
// assert(*max_element(indeg, indeg + n) <= 5);
// cout << dsu.classes() << endl;
// find_3_cycles(n, G, process);
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
cout << "Check array size pls sir" << endl;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 4212kb
input:
1000 3560 603 151 415 20 102 569 895 552 678 734 24 614 689 518 440 223 751 919 223 433 711 551 502 634 706 583 812 501 514 535 780 751 720 530 532 384 888 139 864 791 292 675 171 881 30 592 464 557 280 299 654 650 894 335 250 532 792 10 83 969 118 771 579 300 852 983 243 940 957 939 817 889 911 319...
output:
mark 3 875 366 108 611 733 310
input:
1000 3563 777 626 222 295 811 665 534 338 682 101 833 706 950 155 656 841 184 95 383 221 259 86 815 771 37 355 759 167 402 763 582 250 950 401 802 224 974 277 521 380 368 12 676 977 920 351 831 643 511 688 553 125 506 102 757 70 736 226 733 87 956 373 600 53 201 580 844 267 14 201 583 975 557 937 16...
output:
ok
result:
ok all right
Test #2:
score: 100
Accepted
time: 1ms
memory: 3908kb
input:
1000 2000 457 335 160 497 464 992 892 255 853 3 308 301 970 363 541 299 89 418 425 128 626 827 603 854 484 874 755 295 607 483 798 552 356 850 320 357 254 940 675 901 168 525 301 636 520 555 773 910 343 701 889 966 218 529 909 950 71 64 682 284 424 138 721 792 670 544 386 72 654 909 725 235 592 437 ...
output:
mark 1 861 727
input:
1000 2001 181 711 426 320 503 386 377 826 97 233 231 792 993 1 403 152 381 532 554 117 541 72 291 182 962 916 765 649 252 673 756 751 529 178 731 827 39 689 541 268 139 620 379 851 727 755 622 628 341 884 813 945 564 74 863 90 99 543 25 858 298 450 411 738 758 705 770 529 414 78 838 977 956 965 50 9...
output:
ok
result:
ok all right
Test #3:
score: 100
Accepted
time: 2ms
memory: 4152kb
input:
1000 5000 449 632 597 26 701 322 249 190 411 770 666 596 989 995 112 861 445 818 544 659 24 680 739 593 344 439 193 932 600 526 574 869 216 918 716 793 259 686 555 993 255 578 659 271 328 524 729 672 39 771 241 866 27 790 417 109 56 403 338 299 387 232 280 306 589 794 833 419 900 802 54 697 539 807 ...
output:
mark 4 396 350 593 202 566 748 869 539
input:
1000 5004 258 506 563 742 458 36 208 588 178 845 559 170 361 150 350 788 619 34 977 914 578 699 634 106 213 340 156 570 83 564 647 61 128 762 345 143 821 596 976 995 155 835 60 376 334 471 116 10 467 792 494 48 464 286 956 247 726 21 405 143 612 419 42 981 693 70 407 899 285 697 256 532 649 530 240 ...
output:
ok
result:
ok all right
Test #4:
score: 100
Accepted
time: 1ms
memory: 4208kb
input:
1000 3156 347 398 792 278 754 442 413 757 391 130 636 625 207 437 81 415 47 974 887 779 524 619 379 894 868 594 653 919 29 117 123 867 632 505 648 147 130 420 495 876 637 659 882 348 462 878 282 646 398 525 419 224 926 448 305 934 855 570 396 345 774 918 336 123 502 491 984 783 845 142 790 594 754 4...
output:
mark 3 796 951 881 386 115 418
input:
1000 3159 540 43 167 499 962 403 342 814 154 900 212 990 612 516 712 963 777 715 243 539 28 441 904 773 810 843 856 38 841 423 811 609 729 7 668 435 64 931 392 925 865 396 527 503 798 64 954 311 315 976 508 855 42 940 215 161 501 674 957 617 225 869 919 879 421 610 639 127 923 58 517 216 799 671 470...
output:
ok
result:
ok all right
Test #5:
score: 100
Accepted
time: 1ms
memory: 4264kb
input:
1000 3433 634 21 789 966 541 959 213 381 366 781 107 649 747 122 336 869 222 648 833 972 929 524 712 524 744 525 568 679 634 163 901 501 56 518 128 587 720 117 208 439 860 85 852 168 934 947 34 858 520 568 408 464 232 432 999 504 71 982 957 372 570 436 281 309 410 405 521 275 554 589 4 707 498 148 5...
output:
mark 4 316 156 413 371 631 284 214 797
input:
1000 3437 976 492 771 824 416 864 904 368 376 943 665 576 49 853 251 396 313 452 899 769 437 114 649 427 593 653 514 238 606 993 685 959 722 527 837 342 121 690 919 567 307 925 776 682 505 114 31 681 474 964 669 188 505 579 565 589 743 969 157 802 671 425 441 167 190 992 410 42 947 455 49 960 97 664...
output:
ok
result:
ok all right
Test #6:
score: 100
Accepted
time: 1ms
memory: 4232kb
input:
1000 3057 985 223 432 967 405 822 845 650 893 646 599 718 754 710 333 73 392 355 895 496 200 562 816 36 457 953 9 623 889 662 482 590 249 29 689 694 185 990 285 690 12 323 611 560 903 722 476 86 105 666 441 193 695 640 36 617 840 42 80 527 977 539 606 150 384 585 784 648 919 360 157 532 568 98 995 8...
output:
mark 2 31 485 134 394
input:
1000 3059 29 48 868 224 13 300 440 290 294 719 506 107 14 443 241 921 842 25 722 560 545 503 921 572 590 27 132 790 42 458 25 364 340 372 193 518 42 660 317 815 977 433 761 633 95 970 450 626 333 585 971 732 337 771 63 271 485 551 239 366 440 279 189 644 115 949 138 624 22 995 495 460 191 934 578 21...
output:
ok
result:
ok all right
Test #7:
score: 100
Accepted
time: 1ms
memory: 3968kb
input:
1000 3085 484 405 841 443 661 315 392 941 355 558 523 394 773 929 673 840 5 707 255 610 744 58 301 794 505 33 668 533 787 945 747 810 803 115 340 900 791 909 596 418 129 491 460 698 156 233 664 502 231 465 795 486 829 102 608 212 253 344 419 557 100 421 321 793 207 302 544 479 33 916 736 129 6 156 9...
output:
mark 3 305 664 581 888 729 877
input:
1000 3088 821 665 956 248 417 787 734 95 330 953 826 533 888 479 883 619 174 625 554 613 160 480 570 952 158 636 76 223 518 617 743 937 685 728 427 52 568 778 474 293 247 977 332 533 773 219 31 664 108 860 640 186 907 603 436 948 289 874 710 197 831 963 453 369 44 843 772 765 347 200 330 595 268 65 ...
output:
ok
result:
ok all right
Test #8:
score: 100
Accepted
time: 2ms
memory: 4144kb
input:
1000 4289 963 66 959 467 930 83 419 699 731 948 702 583 699 245 636 721 859 551 377 251 90 889 286 843 908 47 864 979 223 948 269 684 85 579 162 376 414 255 602 884 65 132 842 907 488 360 553 898 649 249 253 711 675 632 629 446 708 413 819 511 512 113 189 76 242 464 828 261 440 737 643 389 75 907 49...
output:
mark 2 632 783 611 963
input:
1000 4291 332 749 188 54 898 992 302 493 586 861 246 17 154 311 838 229 501 316 209 227 784 338 987 999 510 121 91 866 757 8 994 36 972 83 477 824 924 603 496 756 320 32 453 521 433 628 937 526 18 740 686 723 784 591 510 698 317 920 838 799 447 186 474 789 845 588 71 110 337 257 492 670 388 957 527 ...
output:
ok
result:
ok all right
Test #9:
score: 100
Accepted
time: 2ms
memory: 4148kb
input:
1000 4763 544 167 316 76 78 841 699 1 645 745 827 262 568 545 595 81 924 561 108 253 397 626 142 967 613 397 723 633 711 259 363 249 5 436 165 88 178 463 734 529 195 324 135 41 1000 136 215 967 371 638 588 753 542 909 633 106 537 852 111 232 303 500 892 461 868 300 772 667 40 172 956 575 613 163 933...
output:
mark 3 425 983 214 509 571 148
input:
1000 4766 450 16 910 74 103 774 597 624 185 948 625 965 921 271 347 329 156 57 747 193 936 135 594 591 22 837 259 918 762 516 500 479 444 148 161 857 680 705 58 379 897 116 415 90 917 70 78 971 976 767 429 673 66 526 667 621 847 589 37 148 173 872 965 793 396 746 688 388 214 818 820 306 687 862 93 2...
output:
ok
result:
ok all right
Test #10:
score: 100
Accepted
time: 2ms
memory: 4284kb
input:
1000 4250 747 446 769 425 773 753 217 298 217 4 514 774 752 3 905 857 532 410 224 250 367 33 29 541 809 996 76 960 25 603 532 600 518 304 546 95 735 413 312 476 83 534 157 62 170 836 668 976 244 557 972 860 828 170 975 468 677 714 800 170 530 191 216 930 242 728 318 505 269 162 579 963 769 822 171 4...
output:
mark 1 385 5
input:
1000 4251 112 370 102 703 776 233 835 409 598 303 590 999 320 874 639 193 378 512 447 83 308 365 152 512 219 36 14 309 600 242 8 847 585 656 524 394 600 888 342 188 275 604 326 920 728 164 380 74 892 31 797 986 984 629 148 404 377 353 270 344 578 582 5 848 261 174 398 338 494 140 371 94 146 199 45 2...
output:
ok
result:
ok all right
Test #11:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
1000 3336 161 745 81 702 879 347 452 553 809 32 359 925 984 783 558 366 611 89 948 530 565 496 123 348 534 986 991 511 322 407 6 878 20 897 188 150 527 440 487 333 218 572 597 575 308 684 50 780 900 451 763 785 210 682 964 992 811 537 537 167 320 133 523 899 629 732 435 281 826 405 868 567 201 858 2...
output:
mark 4 718 386 688 704 947 565 299 359
input:
1000 3340 374 704 505 741 976 541 334 161 338 863 529 120 166 728 961 763 432 952 34 757 997 947 903 519 820 520 294 110 108 967 256 659 957 285 337 937 681 518 979 589 931 88 913 533 752 222 709 505 843 608 168 502 705 49 897 312 758 572 181 928 300 162 113 469 723 195 585 934 540 513 405 713 921 5...
output:
ok
result:
ok all right
Test #12:
score: 100
Accepted
time: 1ms
memory: 4236kb
input:
1000 3482 910 881 481 989 349 262 963 679 970 752 651 210 86 339 724 310 765 410 118 619 662 351 568 148 292 61 136 385 997 772 210 735 816 310 698 649 581 313 414 280 92 872 965 925 35 930 813 29 617 210 854 940 486 479 412 644 660 623 126 85 664 327 459 165 266 113 108 206 686 660 918 536 173 366 ...
output:
mark 1 333 963
input:
1000 3483 732 216 26 72 633 812 543 565 128 60 104 532 597 504 46 473 87 574 575 144 496 698 646 382 613 317 6 890 739 307 680 811 384 394 455 148 487 770 851 666 52 549 160 733 544 682 624 866 877 240 674 630 256 803 812 625 840 631 346 963 959 707 767 843 220 573 594 935 616 825 391 131 744 173 61...
output:
ok
result:
ok all right
Test #13:
score: 100
Accepted
time: 1ms
memory: 4076kb
input:
1000 2141 358 723 692 581 753 295 864 391 984 462 525 271 508 897 739 537 124 933 577 499 863 37 279 622 361 605 454 951 527 837 1 224 641 404 479 220 931 126 182 719 464 451 805 452 529 800 292 689 17 320 728 790 967 41 412 752 276 535 643 636 611 56 802 414 861 603 857 722 1000 584 435 118 266 392...
output:
mark 3 985 607 442 478 609 790
input:
1000 2144 482 327 721 271 324 265 542 340 774 998 33 221 882 886 960 447 898 211 433 35 745 399 692 986 422 376 816 821 561 879 414 613 27 223 38 338 152 849 453 625 98 796 7 425 257 760 824 441 680 49 476 761 585 315 907 925 938 131 30 914 491 113 788 961 489 597 710 34 409 587 623 686 967 308 948 ...
output:
ok
result:
ok all right
Test #14:
score: 100
Accepted
time: 1ms
memory: 3984kb
input:
1000 2950 244 361 694 442 547 577 545 866 488 207 888 997 263 45 850 200 30 927 195 510 274 582 467 158 664 667 880 573 522 986 736 375 206 326 999 940 875 609 151 161 602 673 664 200 827 579 12 190 300 249 95 502 951 317 669 243 350 841 692 572 619 302 955 999 480 891 109 779 198 893 105 442 214 14...
output:
mark 3 474 1 252 154 651 170
input:
1000 2953 350 585 754 407 289 802 501 671 458 256 116 883 867 14 370 353 816 59 543 229 222 246 204 294 666 263 995 89 208 256 257 570 433 526 293 939 181 66 840 529 60 878 916 716 984 761 343 981 724 3 367 24 462 578 262 59 414 755 113 590 535 476 1 865 22 248 279 841 15 167 771 209 725 260 482 237...
output:
ok
result:
ok all right
Test #15:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
1000 2725 336 461 575 6 961 482 496 574 134 336 671 452 172 957 633 89 909 334 222 155 90 660 201 950 436 671 726 683 487 356 536 389 107 844 403 732 550 608 607 54 718 438 960 144 710 278 398 747 152 501 86 385 34 251 309 822 773 321 329 213 897 948 356 401 290 329 278 591 683 454 122 523 729 436 4...
output:
mark 1 160 401
input:
1000 2726 826 863 860 669 482 188 461 442 496 849 962 420 832 558 899 680 933 304 876 932 6 579 49 750 506 996 166 759 563 508 331 228 210 471 707 306 89 391 16 349 161 923 496 830 591 108 534 553 220 382 489 624 969 790 385 891 900 848 69 837 478 216 455 579 539 29 37 915 554 860 316 683 143 324 33...
output:
ok
result:
ok all right
Test #16:
score: 100
Accepted
time: 1ms
memory: 3948kb
input:
1000 2812 357 725 462 948 927 875 21 284 52 197 457 876 744 315 990 255 660 522 51 971 392 275 736 77 131 216 581 438 495 271 965 111 376 89 824 363 628 13 33 585 836 144 791 404 916 588 668 243 960 335 505 368 744 264 332 893 65 320 205 81 929 44 135 224 306 351 938 505 70 927 825 634 161 492 434 1...
output:
mark 3 972 624 895 828 187 909
input:
1000 2815 548 677 425 134 295 218 332 463 514 383 894 308 900 81 922 400 176 364 59 798 403 327 873 525 996 629 187 626 804 592 99 891 353 321 597 445 745 371 788 328 63 207 321 703 446 391 83 166 347 146 938 32 740 524 279 257 898 307 172 334 672 353 863 603 224 843 172 296 897 177 214 437 205 736 ...
output:
ok
result:
ok all right
Test #17:
score: 100
Accepted
time: 1ms
memory: 3992kb
input:
1000 2616 518 38 164 144 301 140 711 11 36 636 443 779 107 901 467 922 759 675 229 276 467 880 975 435 382 460 238 663 639 927 74 953 777 326 689 944 152 237 501 789 795 889 95 376 390 401 279 64 520 803 273 292 333 454 202 485 860 54 872 641 101 951 236 726 464 847 992 656 576 565 739 176 562 327 2...
output:
mark 2 412 118 301 990
input:
1000 2618 345 700 738 208 607 947 632 659 165 323 876 642 993 338 80 917 709 733 514 965 280 753 15 843 47 645 624 991 415 794 325 151 788 759 21 932 869 528 277 641 792 637 988 918 976 310 929 96 625 162 43 193 691 417 179 744 654 868 523 555 680 739 954 81 676 33 230 213 732 918 592 760 481 154 89...
output:
ok
result:
ok all right
Test #18:
score: 100
Accepted
time: 2ms
memory: 4360kb
input:
1000 4792 659 787 666 143 711 116 742 958 604 434 293 882 175 28 557 753 106 808 527 599 942 249 843 109 174 76 429 255 415 489 463 540 878 235 688 87 629 402 927 418 704 734 886 463 702 992 570 370 492 865 795 889 638 594 887 203 732 896 610 492 960 422 44 255 442 448 426 697 862 351 318 277 783 22...
output:
mark 3 592 110 35 588 548 46
input:
1000 4795 72 88 722 243 805 260 50 598 295 877 373 83 715 329 176 340 196 387 956 159 2 871 737 903 500 615 513 232 167 490 533 887 426 406 375 107 492 552 565 754 733 70 357 489 934 43 447 256 420 199 863 879 144 740 952 343 550 612 706 778 30 629 555 349 402 697 98 849 117 838 528 562 486 627 454 ...
output:
ok
result:
ok all right
Test #19:
score: 100
Accepted
time: 1ms
memory: 4300kb
input:
1000 3724 513 194 958 159 936 285 493 34 668 957 824 152 450 421 92 170 416 782 546 100 698 433 299 741 261 975 661 408 4 927 789 856 52 784 541 618 99 780 527 957 618 74 440 321 839 496 360 484 71 21 149 302 25 505 240 587 584 736 490 934 817 867 682 287 882 528 985 852 201 46 254 112 862 582 379 3...
output:
mark 2 979 737 377 824
input:
1000 3726 257 545 712 740 457 972 157 941 782 667 81 818 469 431 32 340 441 704 304 93 514 298 911 503 97 967 239 357 717 11 108 496 480 902 340 865 920 508 683 106 239 216 956 462 6 261 916 123 586 17 131 313 414 115 284 921 351 805 828 635 13 197 966 380 301 968 922 154 175 703 472 495 603 120 479...
output:
ok
result:
ok all right
Test #20:
score: 100
Accepted
time: 2ms
memory: 4140kb
input:
1000 4188 106 174 116 750 197 421 387 311 48 148 296 628 755 929 804 267 341 16 263 676 486 178 334 256 639 453 183 206 497 528 911 457 854 258 104 922 931 576 725 214 300 460 149 847 754 657 670 983 525 366 475 667 680 376 676 126 929 766 437 821 646 717 578 151 885 981 394 105 264 225 429 390 502 ...
output:
mark 2 877 158 262 654
input:
1000 4190 124 365 552 777 351 939 750 527 559 920 160 76 525 292 753 349 4 209 95 116 435 788 603 700 789 522 380 280 678 489 882 778 312 223 866 738 970 965 895 279 578 808 931 659 909 193 69 249 426 907 695 105 480 686 540 109 387 580 774 301 679 166 131 3 840 645 388 479 300 367 463 209 747 514 6...
output:
ok
result:
ok all right
Test #21:
score: 100
Accepted
time: 1ms
memory: 4252kb
input:
1000 3236 622 762 548 197 457 126 655 978 275 215 472 112 762 998 649 242 890 339 337 1 169 283 365 486 584 324 988 887 406 500 62 591 512 839 76 251 479 635 485 217 961 204 934 8 621 40 374 227 1 403 644 72 758 370 436 494 174 341 770 80 421 125 151 211 405 389 514 637 808 815 131 762 647 518 804 7...
output:
mark 3 301 322 642 415 437 247
input:
1000 3239 797 806 823 240 211 449 697 612 581 389 239 305 947 71 127 894 862 736 716 543 131 22 414 124 436 957 326 789 583 966 725 351 488 284 705 839 193 26 303 321 788 325 85 481 350 53 413 585 222 324 547 186 542 273 542 367 95 353 107 984 394 216 69 975 431 392 991 835 509 204 917 796 813 935 4...
output:
ok
result:
ok all right
Test #22:
score: 100
Accepted
time: 1ms
memory: 4032kb
input:
1000 3299 693 455 906 758 704 271 639 392 910 445 984 43 821 447 3 475 929 500 879 29 243 657 602 744 974 96 879 79 225 9 868 993 115 636 701 248 995 83 781 441 995 320 766 534 432 827 65 632 873 392 231 943 502 170 856 584 368 665 391 797 734 568 538 613 539 984 505 285 965 253 446 107 605 681 216 ...
output:
mark 2 774 474 873 300
input:
1000 3301 938 126 741 12 387 652 828 78 627 911 571 512 227 294 290 451 194 844 983 638 707 311 148 530 17 440 808 338 650 955 877 825 839 816 587 770 855 628 368 694 798 292 821 85 735 576 558 209 938 759 581 936 727 987 879 50 120 177 735 72 197 500 997 461 109 774 961 613 364 867 607 691 735 333 ...
output:
ok
result:
ok all right
Test #23:
score: 100
Accepted
time: 0ms
memory: 4272kb
input:
1000 3482 45 265 363 58 385 372 365 256 659 227 700 636 954 356 708 312 24 144 103 367 797 394 779 615 596 57 546 439 622 318 344 724 27 792 286 475 286 469 581 321 191 79 457 80 357 577 559 587 63 234 982 665 838 402 931 320 724 796 645 275 254 812 283 710 75 269 991 914 888 557 214 416 316 465 197...
output:
mark 3 372 724 696 316 809 361
input:
1000 3485 186 427 612 371 891 660 864 538 497 968 491 936 679 693 864 201 46 605 107 152 559 812 147 971 381 266 944 719 27 474 908 854 779 119 334 272 468 589 148 198 615 811 809 919 929 299 407 912 236 428 217 365 333 726 953 889 146 237 443 682 657 913 230 104 153 853 97 435 616 140 460 573 512 3...
output:
ok
result:
ok all right
Test #24:
score: 100
Accepted
time: 1ms
memory: 4132kb
input:
1000 2311 97 580 515 270 609 837 243 284 715 189 980 486 853 479 235 7 253 300 207 583 282 612 456 80 486 497 503 404 74 701 64 172 583 794 570 655 901 25 14 568 485 218 621 50 253 26 433 784 533 215 134 695 278 364 879 983 690 952 198 197 725 421 95 464 927 999 104 71 752 252 553 356 187 952 38 859...
output:
mark 3 889 185 319 546 690 7
input:
1000 2314 352 855 462 672 981 153 8 103 426 470 344 569 903 148 674 805 181 180 625 109 129 469 307 645 650 7 803 437 286 930 240 100 933 748 146 992 235 494 592 6 244 376 369 211 871 106 609 12 774 39 875 536 75 610 739 885 157 343 268 825 57 219 406 525 436 622 40 654 440 205 483 369 12 914 612 41...
output:
ok
result:
ok all right
Test #25:
score: 100
Accepted
time: 1ms
memory: 4076kb
input:
1000 3896 460 688 426 709 610 203 65 902 606 471 519 789 275 370 86 879 786 822 601 948 312 884 115 372 100 491 967 601 104 750 411 830 571 626 201 132 175 126 678 756 610 712 267 770 853 475 406 479 485 471 479 953 156 968 785 918 61 114 348 147 659 495 709 716 248 599 984 20 728 726 859 759 681 10...
output:
mark 4 358 275 712 590 65 814 600 224
input:
1000 3900 742 623 861 745 673 202 367 848 894 883 586 587 775 186 180 322 14 935 976 535 72 47 962 699 98 938 811 277 487 894 310 220 241 715 114 719 766 469 311 70 203 360 765 626 86 978 573 196 756 536 517 249 607 227 938 982 589 1 994 36 365 297 1 264 788 573 317 999 957 689 7 42 168 171 651 696 ...
output:
ok
result:
ok all right
Test #26:
score: 100
Accepted
time: 2ms
memory: 4068kb
input:
1000 3891 701 522 952 922 356 456 249 391 128 593 9 524 661 405 984 460 440 470 639 699 782 189 537 74 184 399 888 710 975 120 475 924 602 492 200 577 978 478 611 758 886 262 404 313 44 559 170 35 749 501 848 364 6 401 723 549 110 186 281 506 52 379 84 255 755 196 824 136 985 230 523 682 826 823 560...
output:
mark 2 110 229 451 613
input:
1000 3893 308 239 906 576 855 401 871 456 761 481 151 418 316 262 395 230 968 265 366 209 648 416 806 90 469 51 139 551 885 203 696 592 694 106 609 389 673 9 943 668 577 269 925 184 513 927 520 69 153 48 859 422 542 237 868 791 21 677 741 861 388 763 998 999 205 353 655 906 603 952 641 205 963 488 8...
output:
ok
result:
ok all right
Test #27:
score: 100
Accepted
time: 1ms
memory: 4252kb
input:
1000 3265 924 167 3 999 663 583 890 496 619 193 641 842 720 966 650 470 975 552 309 965 968 739 223 474 41 188 279 73 663 940 438 173 385 280 113 178 896 270 15 956 456 196 291 323 392 622 180 781 469 950 685 672 633 436 562 153 407 796 209 630 750 874 190 614 400 306 560 935 235 777 500 785 378 332...
output:
mark 2 93 822 890 888
input:
1000 3267 840 599 212 282 328 540 346 924 492 841 461 613 202 190 578 347 60 359 356 659 250 766 67 64 225 714 970 679 810 974 326 692 886 638 240 378 402 479 597 130 225 927 281 849 79 963 498 397 471 748 598 56 479 778 749 725 820 804 695 140 928 719 283 845 673 485 62 733 238 556 310 648 291 185 ...
output:
ok
result:
ok all right
Test #28:
score: 100
Accepted
time: 2ms
memory: 4332kb
input:
1000 4070 7 484 881 280 807 812 167 913 190 699 784 415 747 45 424 328 414 997 461 463 499 437 173 675 71 525 195 736 428 593 560 602 235 557 91 265 580 422 522 212 50 326 784 938 787 256 963 883 896 902 228 953 997 406 724 753 202 646 93 118 187 777 841 254 573 651 198 821 89 615 124 443 622 120 58...
output:
mark 2 615 474 268 87
input:
1000 4072 370 139 188 415 372 852 788 793 945 841 145 964 33 131 250 810 410 234 106 136 702 46 594 861 934 406 972 967 951 669 868 713 722 81 619 522 598 759 509 796 687 279 905 218 196 536 839 223 502 324 978 610 701 635 816 708 865 594 151 808 985 787 470 624 647 42 907 618 712 958 580 999 418 62...
output:
ok
result:
ok all right
Test #29:
score: 100
Accepted
time: 1ms
memory: 4244kb
input:
1000 3135 679 441 832 386 95 753 472 452 550 725 334 216 547 305 556 805 250 217 546 555 109 827 884 984 297 80 660 821 807 403 301 250 489 275 256 342 841 435 290 873 771 188 76 424 261 377 793 458 945 925 593 432 527 275 971 222 646 49 284 713 3 37 313 181 314 122 257 969 765 89 759 537 273 857 38...
output:
mark 3 857 512 348 569 412 356
input:
1000 3138 853 905 930 978 599 172 751 672 290 682 417 18 848 839 845 328 751 1000 798 864 531 931 792 247 445 58 326 396 245 651 994 672 129 922 540 352 229 502 777 608 571 489 762 234 762 310 463 959 708 610 114 333 692 710 414 891 805 646 461 590 140 246 947 227 689 589 185 650 76 803 297 204 802 ...
output:
ok
result:
ok all right
Test #30:
score: 100
Accepted
time: 2ms
memory: 4340kb
input:
1000 4200 448 409 48 552 204 139 701 128 189 761 181 385 118 653 471 26 968 195 976 473 19 907 837 969 942 346 489 372 710 765 648 339 527 477 990 60 125 276 56 249 110 276 864 906 796 39 940 90 91 628 37 667 25 886 550 150 657 438 553 447 682 141 77 926 647 290 139 792 167 696 965 705 898 787 644 6...
output:
mark 1 965 427
input:
1000 4201 968 760 481 311 737 157 459 517 444 654 5 31 742 400 704 149 684 109 445 81 203 188 635 609 494 745 15 377 363 510 95 432 787 720 17 219 506 389 623 645 166 745 703 771 411 534 689 451 577 838 390 31 935 967 974 802 654 788 1 605 910 38 438 62 195 25 585 513 356 892 660 750 391 77 792 718 ...
output:
ok
result:
ok all right
Test #31:
score: 100
Accepted
time: 1ms
memory: 4032kb
input:
1000 2992 768 684 51 962 667 28 959 894 941 636 131 80 869 468 666 543 262 235 241 428 893 839 546 428 445 949 262 763 896 402 205 644 192 650 177 921 29 488 758 527 657 817 447 872 708 323 759 927 146 982 654 973 787 923 132 163 219 813 822 144 515 188 327 452 542 32 455 122 610 461 203 303 27 766 ...
output:
mark 2 939 10 426 334
input:
1000 2994 996 728 73 311 155 334 275 68 741 290 302 569 958 655 775 386 714 541 992 924 337 226 921 446 639 510 728 124 31 37 117 27 961 203 629 165 679 229 606 685 875 89 895 254 153 736 982 797 780 103 611 404 699 12 110 211 59 888 41 954 206 472 55 331 269 471 145 533 292 346 92 403 325 408 373 7...
output:
ok
result:
ok all right
Test #32:
score: 100
Accepted
time: 1ms
memory: 4076kb
input:
1000 3891 9 226 167 799 23 992 910 468 750 904 219 238 571 266 968 429 700 878 3 169 108 842 736 273 789 322 446 694 869 533 491 744 526 730 190 941 610 146 853 939 824 574 399 326 116 328 687 960 68 460 222 735 64 875 462 627 955 990 5 890 393 852 651 134 683 374 99 609 854 927 357 84 81 455 963 69...
output:
mark 4 267 929 113 446 79 546 775 595
input:
1000 3895 330 308 644 809 856 474 255 914 437 780 618 567 332 807 581 445 625 482 39 566 680 623 497 20 999 168 916 543 976 625 566 142 968 592 52 961 519 154 107 910 950 474 644 946 572 793 270 284 951 404 104 716 281 731 832 104 218 21 92 470 17 400 231 143 932 896 100 836 513 839 424 636 364 344 ...
output:
ok
result:
ok all right
Test #33:
score: 100
Accepted
time: 2ms
memory: 4100kb
input:
1000 4839 721 823 946 252 516 492 460 116 126 30 65 344 134 175 802 407 634 405 799 22 808 599 433 519 711 519 30 52 457 114 41 136 668 659 743 511 155 962 436 847 671 472 549 352 688 699 167 943 467 460 292 150 801 507 559 497 890 264 565 630 672 272 15 90 869 979 853 947 119 690 501 832 285 936 34...
output:
mark 3 155 808 748 691 514 529
input:
1000 4842 591 448 280 878 531 94 305 340 63 550 632 820 980 154 377 614 539 758 528 724 922 73 925 829 206 580 426 899 948 227 935 23 626 870 344 653 728 105 582 947 43 373 442 499 190 400 16 108 746 84 370 984 207 684 723 559 711 634 467 799 953 160 928 692 353 269 230 32 656 733 193 450 861 266 69...
output:
ok
result:
ok all right
Test #34:
score: 100
Accepted
time: 1ms
memory: 3852kb
input:
1000 2034 672 408 42 15 81 165 720 365 17 795 12 752 996 718 504 262 723 214 405 139 860 837 659 586 873 356 313 426 115 550 620 942 287 815 539 518 574 531 642 428 696 628 532 548 164 371 382 434 397 223 880 826 667 805 851 587 387 528 731 649 88 252 738 790 871 539 763 587 116 818 394 292 267 380 ...
output:
mark 3 113 787 476 461 540 795
input:
1000 2037 986 198 322 134 291 293 302 113 287 433 909 695 629 333 845 955 842 902 953 993 711 484 471 26 43 879 716 393 613 48 998 866 66 368 465 670 434 777 58 662 810 964 141 202 179 632 669 446 106 412 108 421 623 68 908 301 805 885 691 197 641 477 365 817 79 177 146 394 331 636 357 114 687 345 6...
output:
ok
result:
ok all right
Test #35:
score: 100
Accepted
time: 1ms
memory: 4136kb
input:
1000 2063 152 651 423 569 82 188 469 837 791 178 513 272 388 461 658 688 805 167 400 258 947 616 803 244 645 636 14 715 355 166 504 598 366 78 611 886 284 952 429 434 138 349 423 520 910 760 263 499 282 106 62 525 765 673 425 636 767 432 378 368 406 797 777 46 728 638 337 259 720 551 32 418 893 567 ...
output:
mark 3 705 660 822 112 355 335
input:
1000 2066 248 802 794 546 623 693 218 571 171 541 680 852 979 593 675 971 626 425 922 91 636 453 442 4 921 981 257 179 379 396 939 740 878 324 493 892 472 749 715 631 223 215 262 244 916 556 995 956 400 919 61 308 550 26 149 650 914 588 53 796 594 614 23 883 160 917 206 66 126 577 347 973 330 336 44...
output:
ok
result:
ok all right
Test #36:
score: 100
Accepted
time: 1ms
memory: 4108kb
input:
1000 2015 735 560 841 818 908 373 452 621 415 440 682 740 879 685 769 787 78 247 709 376 529 131 838 689 352 699 233 54 420 43 675 580 893 682 570 960 886 186 627 685 824 527 285 801 381 190 545 638 803 864 673 545 675 471 539 857 97 929 72 835 176 54 336 134 674 134 214 557 720 131 480 947 842 993 ...
output:
mark 3 783 648 408 22 902 609
input:
1000 2018 934 469 856 292 112 463 9 276 385 391 631 297 792 621 449 281 966 397 826 839 572 126 364 639 569 800 838 541 656 671 791 684 503 372 737 274 826 214 865 523 82 668 737 619 731 427 361 866 989 698 56 306 481 378 952 795 490 100 28 336 755 533 776 595 252 892 451 786 786 238 255 423 541 481...
output:
ok
result:
ok all right
Test #37:
score: 100
Accepted
time: 1ms
memory: 3908kb
input:
1000 2088 740 777 753 465 620 85 563 425 462 640 660 818 506 223 161 680 212 736 832 801 881 351 708 787 743 371 325 128 840 456 832 721 671 768 711 676 967 36 297 541 201 236 348 983 794 78 832 912 840 569 671 857 357 781 263 615 505 283 760 980 279 519 225 480 387 569 407 877 132 284 863 892 600 9...
output:
mark 2 256 52 663 837
input:
1000 2090 215 124 152 914 778 243 890 209 54 631 988 975 461 465 594 421 763 564 358 961 744 810 367 230 580 437 123 377 470 672 139 576 539 394 135 231 607 178 958 565 617 434 588 122 448 735 71 917 777 801 989 360 929 539 291 55 146 706 722 284 486 94 167 615 307 755 275 95 323 470 262 707 688 657...
output:
ok
result:
ok all right
Test #38:
score: 0
Wrong Answer on the first run
input:
1000 2095 820 62 50 81 933 467 775 61 743 331 914 662 41 547 91 695 965 431 215 837 251 67 840 532 289 599 112 235 939 390 316 769 806 938 477 138 916 693 337 373 776 82 795 276 390 706 679 304 951 493 51 821 702 85 6 852 586 638 125 198 298 989 235 203 294 967 785 338 923 718 907 138 534 232 735 70...
output:
ok
input:
output:
result:
wrong answer Token "ok" doesn't correspond to pattern "mark"