QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #679916 | #4364. Ceiling Function | LJY_ljy | AC ✓ | 1ms | 4164kb | C++11 | 2.1kb | 2024-10-26 19:11:48 | 2024-10-26 19:11:50 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const long long MAXN = 110;
long long a[MAXN][MAXN], n, k, eid;
vector<long long> V[MAXN];
struct node {
long long lc, rc, v, siz;
} Tree[MAXN][MAXN];
inline long long read() {
long long x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void Insert(long long p, long long x, long long order) {
Tree[order][p].siz++;
if (x >= Tree[order][p].v) {
if (Tree[order][p].rc)
Insert(Tree[order][p].rc, x, order);
else {
eid++;
Tree[order][p].rc = eid;
Tree[order][eid].v = x;
Tree[order][eid].siz = 1;
return;
}
} else {
if (Tree[order][p].lc)
Insert(Tree[order][p].lc, x, order);
else {
eid++;
Tree[order][p].lc = eid;
Tree[order][eid].v = x;
Tree[order][eid].siz = 1;
return;
}
}
}
bool same(long long i, long long j, long long eid1, long long eid2) {
if (Tree[i][eid1].siz != Tree[j][eid2].siz) return false;
if (Tree[i][eid1].siz == 0 && Tree[j][eid2].siz == 0) return true;
long long x = Tree[i][eid1].lc, y = Tree[j][eid2].lc;
bool flag = same(i, j, x, y);
if (!flag) return flag;
x = Tree[i][eid1].rc, y = Tree[j][eid2].rc;
flag = same(i, j, x, y);
return flag;
}
int main() {
n = read(); k = read();
for (long long i = 1; i <= n; i++) {
for (long long j = 1; j <= k; j++)
a[i][j] = read();
}
for (long long i = 1; i <= n; i++) {
eid = 1;
Tree[i][eid].v = a[i][1];
Tree[i][eid].siz = 1;
for (long long j = 2; j <= k; j++)
Insert(1, a[i][j], i);
}
long long cnt = 1;
V[1].push_back(1);
for (long long i = 2; i <= n; i++) {
bool flag = false;
for (long long j = 1; j <= cnt; j++) {
long long x = V[j][0];
if (same(x, i, 1, 1)) {
V[j].push_back(i);
flag = true;
}
}
if (!flag) {
cnt++;
V[cnt].push_back(i);
}
}
printf("%lld\n", cnt);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
5 3 2 7 1 3 1 4 1 5 9 2 6 5 9 7 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 4 3 1 2 40000 3 4 2 1 33 42 17 23
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
2 2 1 2 2 1
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
24 4 2 1 4 3 3 4 2 1 2 3 1 4 3 2 4 1 4 1 3 2 2 3 4 1 1 2 3 4 1 2 4 3 4 3 2 1 3 2 1 4 3 1 4 2 2 4 3 1 1 4 3 2 4 1 2 3 1 4 2 3 4 2 3 1 4 3 1 2 3 1 2 4 2 4 1 3 3 4 1 2 1 3 4 2 2 1 3 4 4 2 1 3 1 3 2 4
output:
14
result:
ok single line: '14'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
50 20 163 166 173 175 185 192 194 200 208 211 221 230 239 247 255 261 271 277 280 283 110 115 117 121 130 133 138 144 151 159 165 175 181 191 198 205 215 222 224 228 189 191 197 206 208 216 218 225 227 229 233 242 246 248 256 259 269 276 284 293 187 197 207 215 218 222 229 238 240 244 250 254 256 26...
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
50 20 1219 1217 1214 1204 1196 1188 1183 1175 1169 1167 1157 1151 1146 1136 1132 1125 1123 1117 1107 1105 1266 1262 1252 1248 1241 1232 1224 1218 1216 1207 1204 1197 1187 1177 1171 1163 1161 1157 1148 1139 1269 1259 1249 1247 1241 1233 1226 1222 1218 1208 1206 1198 1193 1188 1182 1177 1170 1168 1160...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
50 20 17 20 16 18 19 15 11 13 14 10 12 6 2 1 4 3 5 9 8 7 17 20 18 16 15 19 11 13 14 10 6 2 1 4 3 5 9 8 7 12 17 20 16 15 11 18 19 10 6 13 2 12 9 1 4 3 5 8 7 14 17 16 15 20 18 11 13 10 12 6 14 9 19 2 1 4 3 5 8 7 17 16 15 20 18 11 19 10 6 13 14 12 2 1 4 3 5 9 8 7 17 20 16 18 15 11 13 10 14 19 12 6 2 1 ...
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
50 7 7 6 3 5 4 2 1 1 3 2 4 7 5 6 4 7 1 2 5 3 6 5 1 6 7 2 4 3 1 3 2 5 6 4 7 6 7 1 5 4 2 3 1 3 7 2 4 5 6 1 2 3 5 4 6 7 5 1 7 2 6 3 4 7 1 6 2 3 5 4 3 4 1 2 5 7 6 1 2 7 6 5 3 4 3 7 2 4 1 5 6 6 7 3 5 2 4 1 5 1 3 6 2 4 7 7 6 1 5 2 4 3 1 5 4 7 6 2 3 4 2 1 7 3 5 6 1 2 5 7 3 6 4 4 3 1 7 5 2 6 2 1 3 4 6 5 7 2...
output:
50
result:
ok single line: '50'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10 10 500 501 499 502 503 504 505 498 506 497 585 584 583 582 581 586 580 587 588 589 872 873 871 870 874 875 869 876 868 867 114 115 113 116 117 112 111 110 109 118 143 142 144 145 141 146 147 148 149 150 965 964 966 967 968 969 970 971 963 962 933 934 935 936 932 931 937 930 929 928 425 424 423 42...
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 10 828 827 829 826 824 825 830 832 833 834 426 428 429 427 425 423 430 431 432 424 419 420 418 421 417 422 423 416 424 425 947 945 944 946 943 948 950 949 942 951 93 91 94 95 92 96 97 90 98 89 27 29 31 32 33 30 28 26 34 25 214 212 213 215 216 211 217 210 218 209 223 221 220 219 222 224 218 225 22...
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
10 10 468 472 471 474 473 469 464 466 467 470 258 255 252 247 242 237 236 241 240 235 930 926 924 927 932 928 925 929 931 923 992 996 999 998 993 1000 1001 997 994 991 854 859 856 860 861 864 858 862 867 863 821 820 823 824 819 822 818 816 825 817 378 381 380 377 375 376 373 370 374 379 137 139 135 ...
output:
10
result:
ok single line: '10'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
10 10 304 312 310 303 305 311 302 306 297 293 446 443 442 436 444 449 448 447 457 462 151 150 153 160 166 173 182 184 191 201 657 666 664 673 668 674 684 681 676 682 509 506 513 519 516 505 498 492 485 490 294 289 296 297 299 290 280 291 281 273 1060 1055 1050 1042 1033 1031 1021 1029 1034 1032 573 ...
output:
10
result:
ok single line: '10'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
50 20 2441 2440 2442 2439 2438 2443 2444 2445 2446 2437 2436 2447 2435 2434 2448 2449 2450 2433 2451 2432 3315 3316 3314 3317 3313 3312 3318 3311 3319 3320 3310 3321 3322 3323 3324 3309 3308 3307 3306 3305 4723 4722 4724 4725 4721 4726 4727 4728 4720 4719 4718 4729 4730 4731 4732 4733 4734 4735 4717...
output:
9
result:
ok single line: '9'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
50 12 3380 3379 3381 3382 3378 3383 3384 3385 3386 3387 3377 3376 2278 2277 2276 2279 2275 2274 2280 2281 2282 2273 2272 2271 3566 3567 3568 3569 3570 3571 3572 3573 3565 3574 3564 3575 4854 4853 4855 4852 4851 4850 4856 4857 4849 4858 4848 4859 3854 3853 3855 3852 3856 3857 3858 3851 3850 3859 3860...
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
50 12 4009 4010 4008 4006 4004 4003 4002 4005 4007 4001 4011 4000 1143 1141 1142 1144 1140 1145 1139 1137 1135 1133 1131 1129 5009 5011 5008 5006 5005 5004 5007 5010 5003 5012 5002 5013 2270 2268 2267 2269 2266 2265 2263 2271 2264 2272 2273 2262 4568 4567 4569 4566 4570 4572 4573 4571 4574 4576 4575...
output:
43
result:
ok single line: '43'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
50 12 9790 9773 9776 9752 9793 9852 9884 9953 9866 9949 9976 9956 8582 8518 8592 8646 8621 8627 8724 8743 8751 8758 8800 8783 5753 5775 5752 5768 5691 5666 5603 5695 5622 5684 5648 5668 5472 5572 5602 5596 5681 5754 5818 5776 5785 5798 5774 5807 7703 7732 7826 7857 7805 7730 7829 7844 7889 7957 7976...
output:
50
result:
ok single line: '50'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
9 15 644 643 642 640 645 641 639 646 638 647 637 636 648 635 649 577 579 576 578 575 573 572 574 571 580 581 570 582 584 585 837 835 838 839 840 836 834 841 833 831 832 830 842 843 829 225 224 222 220 218 219 217 221 216 223 215 226 228 227 229 194 192 190 189 188 191 193 187 195 196 186 197 199 185...
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
32 6 3087 3084 3088 3089 3092 3093 191 190 189 192 188 193 1800 1798 1801 1802 1804 1803 790 788 786 789 791 792 3092 3093 3094 3095 3091 3088 1711 1710 1707 1706 1708 1709 325 324 327 330 332 329 1535 1536 1534 1533 1537 1532 1714 1716 1719 1718 1720 1721 3104 3102 3105 3103 3100 3098 1956 1958 195...
output:
23
result:
ok single line: '23'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
44 6 676 677 675 678 674 671 3557 3555 3554 3553 3552 3556 2064 2061 2058 2057 2054 2059 2117 2114 2116 2119 2122 2125 4273 4272 4270 4274 4276 4278 3190 3192 3189 3187 3184 3185 1940 1941 1939 1937 1934 1938 278 281 280 279 276 282 3493 3490 3488 3485 3484 3486 3936 3933 3931 3934 3935 3932 327 329...
output:
24
result:
ok single line: '24'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
8 6 189 187 184 182 185 181 444 445 446 443 447 450 162 161 158 155 152 149 781 783 782 780 778 776 48 51 50 47 52 49 628 626 623 621 624 620 75 76 77 79 80 82 715 713 716 714 712 711
output:
7
result:
ok single line: '7'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
9 14 321 325 324 326 323 327 322 320 316 328 332 329 319 330 146 145 147 148 144 149 143 142 150 154 141 151 155 152 397 400 404 402 401 398 395 393 389 390 388 391 387 392 66 64 63 65 62 58 67 68 61 59 69 60 57 70 57 56 60 55 58 61 59 63 54 62 53 64 68 72 308 309 312 314 313 310 311 307 315 316 306...
output:
9
result:
ok single line: '9'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
29 6 1553 1549 1547 1550 1546 1548 486 484 482 485 488 489 1662 1661 1663 1660 1664 1659 2250 2254 2251 2248 2244 2245 2750 2746 2748 2744 2743 2740 935 932 929 928 930 927 574 576 572 575 578 581 1770 1766 1763 1759 1761 1762 1264 1260 1256 1257 1258 1255 656 655 659 657 658 662 1638 1635 1637 1633...
output:
26
result:
ok single line: '26'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
20 10 778 779 777 780 776 775 781 774 782 773 1343 1342 1344 1341 1345 1340 1337 1338 1335 1336 1411 1409 1408 1410 1407 1406 1404 1403 1401 1405 1018 1016 1019 1020 1017 1015 1014 1013 1021 1022 108 106 105 103 104 102 107 109 101 110 1897 1900 1902 1905 1901 1903 1899 1904 1898 1906 1157 1155 1152...
output:
20
result:
ok single line: '20'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
39 13 2727 2728 2729 2726 2724 2730 2725 2723 2731 2732 2734 2722 2733 3745 3744 3743 3746 3742 3741 3747 3749 3740 3748 3739 3750 3752 868 870 867 866 869 871 873 875 874 876 872 877 879 1740 1739 1738 1741 1737 1735 1734 1736 1742 1743 1733 1744 1745 1179 1178 1180 1177 1181 1183 1185 1186 1184 11...
output:
38
result:
ok single line: '38'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 11 39 42 38 41 37 40 36 43 44 35 34 32 33 31 34 30 29 26 27 35 38 36 249 250 247 251 252 248 246 243 245 253 244
output:
3
result:
ok single line: '3'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
28 8 273 269 272 268 274 271 275 270 1668 1667 1670 1671 1674 1677 1676 1678 1570 1573 1575 1572 1569 1571 1574 1568 939 936 933 932 931 928 929 934 2410 2407 2404 2405 2406 2409 2408 2403 1057 1058 1059 1056 1052 1048 1051 1050 2634 2632 2635 2631 2630 2629 2633 2628 154 153 155 156 152 157 159 151...
output:
28
result:
ok single line: '28'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
36 11 247742 130829 275113 242948 114559 286597 884749 58988 251098 70739 171032 718254 199842 831195 818792 102602 967907 705231 967306 495651 561043 635137 854140 814362 533159 766152 343565 887880 422275 649358 12577 179287 464073 704693 491665 416766 970131 653860 511919 714071 318331 886770 810...
output:
36
result:
ok single line: '36'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
5 13 691000 312459 864340 724916 580885 844519 99533 541842 240449 979929 511143 492963 971894 894262 429904 365612 631300 72419 856441 821931 107186 773204 509318 930981 337596 369119 677791 123019 586555 379068 621988 354568 750179 158940 730557 683434 378342 635810 796047 470826 450549 351554 923...
output:
5
result:
ok single line: '5'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
13 16 259383 193026 605549 214799 324260 221230 10505 301849 13668 993371 845320 754062 411606 199594 306491 650306 219954 642324 635742 282969 952342 61672 133426 734878 161389 532975 236920 826483 333630 648240 201484 256355 472719 992015 128283 547603 181555 605904 218434 197656 5111 571449 55725...
output:
13
result:
ok single line: '13'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
14 3 378366 667919 451808 816294 440648 710469 340297 301777 702118 357048 910991 103978 534321 947032 399657 968170 803894 235089 227831 136972 654158 228379 373428 945452 423772 886640 252343 660170 316643 929561 408166 98413 441410 442082 416439 717540 560333 491756 511076 71656 443656 164897
output:
5
result:
ok single line: '5'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
39 12 530882 766722 646975 686391 614284 466972 894734 936122 560021 814873 893936 813721 75555 668210 26729 175488 403568 45698 846811 503661 802591 756022 944459 927225 665945 93153 250637 334389 934024 344876 122959 663215 450352 410730 640832 945812 415013 513162 540763 650159 554349 154854 5142...
output:
39
result:
ok single line: '39'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
16 8 362259 667550 86919 675944 464418 866883 929928 142871 55451 548831 915786 977828 892420 245562 446507 274251 847888 573473 669717 900372 78662 257982 79289 37514 344016 247458 699435 716483 802 620645 99418 406942 908357 469349 43754 825932 460671 897706 701488 8644 616417 154346 523529 338970...
output:
16
result:
ok single line: '16'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
16 11 665939 492184 616830 404345 326192 180010 542712 700697 85509 814214 479737 353888 837889 79852 413992 891771 984867 283370 788865 53692 473137 808651 723937 623254 951378 448941 601328 712772 223049 322480 763627 249866 69006 514891 285069 47124 882891 646200 574553 660858 735088 183184 50247...
output:
16
result:
ok single line: '16'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
11 6 295566 302880 479055 839113 756317 455565 713193 447663 866193 798917 194428 351354 878182 225594 113195 217174 350249 987924 21014 64771 623040 686842 401464 537517 590480 183152 89568 140313 158734 376666 898377 820604 560486 150111 688920 3494 88513 624297 472883 153691 451703 117832 715001 ...
output:
11
result:
ok single line: '11'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
12 7 291388 78619 945367 867244 966006 445425 648278 593908 292543 111985 66151 846350 93727 765366 790325 950781 514834 937591 3749 922704 723259 788203 256144 944013 558440 591881 795482 173898 324286 386153 624883 475996 120001 18438 300906 819238 889730 825701 320745 611539 492070 410382 528593 ...
output:
12
result:
ok single line: '12'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
39 17 931325 783422 186569 310474 651619 377800 4967 617414 144864 834067 11324 882394 274157 932644 226770 237753 63615 141992 628841 881345 715297 169213 264860 20504 999661 997674 147763 60339 140646 414960 357124 343472 130101 491064 920070 999715 308735 558379 498355 838638 559455 862433 276889...
output:
39
result:
ok single line: '39'
Test #38:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
50 20 286431 576787 71995 535882 304791 303476 103746 221970 448849 445816 520734 516513 112211 463017 757962 544313 130870 47943 408306 295914 972643 210406 813121 79614 830141 261857 224151 710916 404701 566334 165786 691900 967288 70368 572772 455260 383965 621411 777754 303677 686619 741336 2141...
output:
50
result:
ok single line: '50'
Test #39:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
50 1 999951 999952 999953 999954 999955 999956 999957 999958 999959 999960 999961 999962 999963 999964 999965 999966 999967 999968 999969 999970 999971 999972 999973 999974 999975 999976 999977 999978 999979 999980 999981 999982 999983 999984 999985 999986 999987 999988 999989 999990 999991 999992 9...
output:
1
result:
ok single line: '1'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
50 3 1 1000000 500022 999998 500028 6 3 999989 500022 500013 999989 10 500029 999988 10 500024 8 999997 500027 6 999988 500019 10 999996 500015 3 999988 500029 3 999992 4 999990 500020 9 999993 500017 500017 999997 1 4 999998 500025 999989 9 500012 500026 1 999992 2 500017 999992 999989 9 500011 999...
output:
5
result:
ok single line: '5'