Untitled
unknown
plain_text
2 years ago
20 kB
58
Indexable
--------------MAIN-------------------
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N, int mId[], int mLocation[]);
extern int add(int mId, int mLocation);
extern int remove(int mStart, int mEnd);
extern int install(int M);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_ADD 2
#define CMD_REMOVE 3
#define CMD_INSTALL 4
static bool run() {
int q;
scanf("%d", &q);
int n, mid, mloc, mstart, mend, m;
int midArr[100], mlocArr[100];
int cmd, ans, ret = 0;
bool okay = false;
for (int i = 0; i < q; ++i) {
scanf("%d", &cmd);
switch (cmd) {
case CMD_INIT:
scanf("%d", &n);
for (int j = 0; j < n; ++j) {
scanf("%d %d", &midArr[j], &mlocArr[j]);
}
init(n, midArr, mlocArr);
okay = true;
break;
case CMD_ADD:
scanf("%d %d %d", &mid, &mloc, &ans);
ret = add(mid, mloc);
if (ans != ret)
okay = false;
break;
case CMD_REMOVE:
scanf("%d %d %d", &mstart, &mend, &ans);
ret = remove(mstart, mend);
if (ans != ret)
okay = false;
break;
case CMD_INSTALL:
scanf("%d %d", &m, &ans);
ret = install(m);
if (ans != ret)
okay = false;
break;
default:
okay = false;
break;
}
}
return okay;
}
int main() {
setbuf(stdout, NULL);
freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++) {
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
--------------USER-------------------
#define MAX_N 24105
#define HASHSIZE 25013
#define NULL 0
struct Building {
int id, pos;
Building* next;
} nodePool[MAX_N];
int poolIdx;
int N;
Building* newBuilding(int id, int pos)
{
nodePool[poolIdx].id = id;
nodePool[poolIdx].pos = pos;
return &nodePool[poolIdx++];
}
Building* buildings[MAX_N]; //buildings that be sorted by increased order of location
Building* HashMap[HASHSIZE];
void addToHashMap(Building* building)
{
int index = building->id % HASHSIZE;
building->next = HashMap[index];
HashMap[index] = building;
}
Building* findById(int id)
{
for (Building* building = HashMap[id % HASHSIZE]; building; building = building->next)
if (building->id == id)
return building;
return NULL;
}
int searchIndex(int val, bool isFindFloor)
{
int low = 0, high = N - 1, mid;
while (low <= high) {
mid = (low + high) >> 1;
if (val == buildings[mid]->pos)
return mid;
if (val > buildings[mid]->pos)
low = mid + 1;
else
high = mid - 1;
}
return isFindFloor ? high : low;
}
int floorIndex(int val)
{
return searchIndex(val, true);
}
int ceilingIndex(int val)
{
return searchIndex(val, false);
}
void addToPosition(Building* building, int pos)
{
for (register int i = N; i > pos; i--) {
buildings[i] = buildings[i - 1];
}
buildings[pos] = building;
N++;
}
void removeByIndex(int start, int num)
{
for (register int i = start; i < start + num; i++) {
buildings[i]->pos = 0;
}
N -= num;
for (register int i = start; i < N; i++) {
buildings[i] = buildings[i + num];
}
}
void init(int N, int mId[], int mLocation[])
{
poolIdx = 0;
for (register int i = 0; i < HASHSIZE; i++)
HashMap[i] = NULL;
::N = N;
for (register int i = 0; i < N; i++) {
buildings[i] = newBuilding(mId[i], mLocation[i]);
addToHashMap(buildings[i]);
}
//Bubble sort is enough for 100-elements array
Building* tmp;
for (int i = 0; i < N - 1; ++i) {
for (int j = i + 1; j < N; ++j) {
if (buildings[i]->pos > buildings[j]->pos) {
tmp = buildings[i];
buildings[i] = buildings[j];
buildings[j] = tmp;
}
}
}
}
int add(int mId, int mLocation)
{
Building* building = findById(mId);
if (building) { //building with mId already created
if (building->pos > 0) //building mId still exist in list
removeByIndex(searchIndex(building->pos, true), 1);
building->pos = mLocation;
} else {
building = newBuilding(mId, mLocation);
addToHashMap(building);
}
int addedPlace;
if (mLocation < buildings[0]->pos)
addedPlace = 0;
else if (mLocation > buildings[N - 1]->pos)
addedPlace = N;
else
addedPlace = ceilingIndex(mLocation);
addToPosition(building, addedPlace);
return N;
}
int remove(int mStart, int mEnd)
{
if (mStart > buildings[N - 1]->pos || mEnd < buildings[0]->pos)
return N;
int startIndex = mStart > buildings[0]->pos ? ceilingIndex(mStart) : 0;
int endIndex = mEnd < buildings[N - 1]->pos ? floorIndex(mEnd) : N - 1;
if (startIndex <= endIndex)
removeByIndex(startIndex, endIndex - startIndex + 1);
return N;
}
int install(int M)
{
int low = 1;
int high = buildings[N - 1]->pos - buildings[0]->pos;
int ret = low;
int mid, cnt, lastLoc;
while (low <= high) {
mid = (low + high) >> 1;
cnt = 1;
lastLoc = buildings[0]->pos;
for (register int i = 1; i < N; i++) {
if (buildings[i]->pos - lastLoc >= mid) {
cnt++;
lastLoc = buildings[i]->pos;
}
}
if (cnt >= M) {
if (mid > ret)
ret = mid;
low = mid + 1;
} else
high = mid - 1;
}
return ret;
}
--------------INPUT------------------
25 100
8
1 4 200 13 700 2 500 7 300 22
4 3 9
2 600 25 5
4 3 11
2 200 18 5
4 4 5
3 1 7 3
4 2 7
100
1 10 6932607 654583776 9283574 109335179 3799193 794471794 3550168 772930245 639546083 381971572 1308586 719212847 7490781 343235942 1588076 538207305 6568711 956612808 8911646 371038355
2 3550168 282976735 10
3 149811982 525023893 6
2 4858423 86234552 7
2 6568711 269544020 7
2 1297328 852280509 8
2 5269673 235296706 9
2 5935358 154978291 10
2 179349311 49906080 11
2 2438588 809784281 12
2 932631941 214206318 13
4 8 57808715
2 6476176 786859805 14
2 8634633 65456802 15
2 4176862 518465363 16
4 6 105072211
3 147225606 365097111 12
2 3550168 710661177 13
3 468395384 582076065 11
2 5224017 450231882 12
2 797446 286635611 13
2 2178983 129653352 14
2 755512836 910563713 15
2 353928109 24109174 16
2 6226546 867900631 17
4 13 20318173
2 6329521 979471146 18
4 5 163596271
2 2438588 69211756 18
2 1151304 681257077 19
3 252768740 556514971 17
2 9935373 602048342 18
2 7811282 948892727 19
2 8500675 722606548 20
2 8533680 458640445 21
2 64444969 588890946 22
2 4435710 546923891 23
2 1588076 989437119 24
4 21 9965973
2 3055193 84110002 25
2 5559406 462898467 26
2 9108591 591118864 27
2 8721068 300616841 28
3 231728136 314696224 27
2 3136289 316033114 28
2 9383062 34331691 29
2 4960631 691606264 30
2 7238036 587721681 31
2 1366653 627206534 32
2 130699010 393225127 33
4 29 3754954
2 1151304 519516929 33
3 105643362 569093680 25
2 1152281 199574642 26
2 4380078 614247907 27
4 5 175465468
2 2851037 401018470 28
2 8876770 4877575 29
2 1066259 550912356 30
3 601626335 751254658 22
3 429205036 658559401 18
2 4606776 682978853 19
2 2536849 597380490 20
2 6264006 72727195 21
4 13 20777750
2 5728981 143024638 22
2 1859578 304452159 23
2 6277835 460325308 24
2 5269673 504561304 25
2 1303092 237498097 26
2 9986333 67381286 27
2 4388002 681362887 28
2 7621587 21151524 29
2 312064 24007245 30
2 6820921 949466386 31
2 9690318 795771907 32
2 5364047 264753520 33
3 3579153 24109174 29
2 8400807 510771048 30
2 2536849 63853828 30
2 5573344 899723437 31
2 328857 114364402 32
2 9500590 998779747 33
3 1 49906080 31
2 2816733 605435878 32
2 259938 191197831 33
3 558270622 848864256 27
2 7363039 712543808 28
2 8850012 632772089 29
2 4349989 400886030 30
2 7423242 279480591 31
2 6396955 16227148 32
2 5531816 95510485 33
2 1438273 966414458 34
4 22 13056688
2 5747388 389703257 35
2 4574853 869077486 36
2 2908778 777102959 37
2 8425851 857485100 38
2 9601032 269886005 39
200
1 15 8846163 844795556 9737050 512736543 3187149 469088278 1552924 93647033 7135863 991920632 971470 2113923 6531793 785196746 4269168 232732669 1791195 734568204 2482946 419933863 136221845 153600318 1531140 530212353 1916927 806766048 673506550 536236683 826551065 915476850
2 7581102 424402659 16
3 142182314 184874217 15
2 971470 890270267 15
2 511932423 731206856 16
2 287716 888202337 17
2 8656397 732692950 18
2 2477394 69201591 19
2 7166147 920627284 20
2 6245168 360712893 21
2 9511593 74319298 22
2 2508670 457602035 23
2 626239 905210272 24
2 9071804 144407001 25
2 3016965 37262702 26
4 12 50759968
3 323779063 639464071 18
3 234907395 351204783 18
2 6843656 133700021 19
2 540485409 781949658 20
3 108395357 265880323 17
2 7312274 440287607 18
2 8548355 310679060 19
3 468223831 494825927 19
2 1020300 830923113 20
3 5977712 137775253 16
2 3281153 782989754 17
2 1624438 192992779 18
2 9798231 411863384 19
2 9835636 712951985 20
2 652539357 486664422 21
2 8656397 292367970 21
4 12 24816390
2 668772 357757921 22
2 490509 33360726 23
2 9480530 541938743 24
2 3486531 129816532 25
2 6452016 863343165 26
2 8441385 876441922 27
2 6907646 755620723 28
2 486240959 929952032 29
4 10 65389951
2 5827762 694887831 30
2 40611 679473588 31
4 6 159632053
3 239543973 453290315 26
2 2140706 72753223 27
2 1372883 565128612 28
2 1624064 953722573 29
2 624569 33309586 30
2 14010318 542948483 31
4 19 21052519
2 3022205 780482438 32
2 511932423 994835714 32
2 29886 564559923 33
2 5896959 847860960 34
2 7828476 300334617 35
2 8213317 317113518 36
2 9652906 975852079 37
2 2477394 586154811 38
2 5555975 844432328 39
2 3417700 221957473 40
2 7828476 861011853 40
2 4588409 506934098 41
2 937958798 786676547 42
4 14 44216068
4 29 10266578
2 9718939 626527692 43
2 5464872 26685013 44
2 905537 34131706 45
2 5477814 324823627 46
2 1555863 902880408 47
3 270402977 609923285 38
2 881641360 817754141 39
2 370953 314757026 40
2 6224990 800872531 41
4 13 45518809
2 5179213 754430614 42
2 7197842 94309495 43
2 8154883 212661524 44
3 51066701 159282490 41
2 490509 849032076 41
2 83432 222435605 42
2 7581102 816951937 43
3 15818590 280943240 36
2 1552924 996706201 37
2 767813 822069294 38
2 5988394 580659119 39
2 8253115 757669228 40
3 1 580659120 38
2 554702494 428924179 39
3 22839194 311237217 39
2 2797419 190147932 40
2 2328888 572102053 41
2 4871185 320124682 42
2 8483014 326098459 43
2 338791 841208616 44
2 8128452 740155201 45
2 9550701 517130550 46
2 3412146 607495831 47
2 9018915 39164596 48
4 34 5117357
4 32 5586997
2 253100 636959625 49
4 23 17007935
2 8833491 71631524 50
2 3379584 371624397 51
2 8113593 603858066 52
2 4418638 87008131 53
2 5015759 747411184 54
2 2257420 302259689 55
2 9851157 245963070 56
4 33 10431933
2 9366880 63612973 57
2 5292953 468519282 58
3 347590853 607100019 52
2 5554474 431029551 53
2 122759227 783023340 54
2 701201608 418916597 55
2 4425313 349983002 56
2 6347990 929305579 57
2 1758903 977741240 58
4 22 23395158
4 22 23395158
2 7768624 575178429 59
2 6239657 902149058 60
2 7370110 800437235 61
2 9929919 472497568 62
2 5467708 107809753 63
2 7683205 154627438 64
2 1759978 926110191 65
2 7968123 614337708 66
2 2445832 728675253 67
2 783649 237977306 68
2 3191958 952416939 69
3 751465081 790758948 60
2 9897859 481383444 61
2 2952560 530272125 62
4 49 3841841
2 5901479 806374504 63
2 5521156 5067137 64
2 4883117 770131574 65
2 2074994 76644055 66
2 981212259 222962164 67
3 285449391 673858355 53
2 1328492 409576393 54
3 993741999 1000000000 52
2 6536545 184937626 53
2 5189078 586110827 54
2 3811639 67736376 55
4 32 7985764
2 8154883 961850890 56
3 2671679 67736376 52
2 5536681 615929154 53
2 796798 615141747 54
2 4200639 265948960 55
2 1923644 543156569 56
2 3019781 182658798 57
4 40 5117357
2 6371984 414590109 58
2 2584457 741036578 59
3 284357437 369991591 59
2 354441818 446154783 60
2 1218219 29762076 61
2 7954680 94502757 62
2 3623249 818285514 63
2 9342726 323424219 64
4 55 1305634
2 9227541 867931710 65
2 6422842 705880959 66
2 2091403 729519100 67
2 2542936 816695749 68
3 697078132 1000000000 24
2 4032861 958048870 25
2 4825186 158767367 26
3 674021662 759868389 24
2 2755039 731448000 25
3 574828267 722139745 22
2 2501688 427901989 23
2 6819473 665528714 24
2 322758 308436123 25
2 1166823 58492328 26
2 9897859 853322052 27
2 8917152 805094381 28
2 793602265 869325874 29
2 8199534 625290915 30
2 5834991 886597008 31
2 9038508 632947209 32
3 835898658 1000000000 28
2 1298081 941651418 29
2 7954680 664207510 29
2 1797138 428122743 30
4 11 63304272
3 906757946 1000000000 29
3 568005507 759580712 24
2 5189078 612312169 25
2 6256789 604027326 26
2 8920122 805853439 27
3 622095734 630074501 27
3 365105907 765272397 19
300
1 20 9078725 31736366 1173876 401594289 7799599 41952592 3319142 606679227 969209545 119761250 6700360 462862197 6035859 794182372 2770714 331348063 402317 577699926 29780828 537371129 3227703 104740920 76174 448196291 7036689 986752266 6711728 112439613 8138139 242966860 5624770 947916263 2024021 608103294 9008196 799505217 36896191 12880416 1189942 578973131
2 801048215 911979032 21
2 177844 762754161 22
2 753181 456813990 23
3 291636863 644394913 13
2 383838 412298195 14
4 11 15020330
2 5720013 691819542 15
2 871826 15042551 16
2 8609923 642722964 17
3 629252047 729720624 15
2 8995468 770687977 16
4 5 169331335
2 9611059 325869700 17
2 4902624 486895149 18
2 24857 748566386 19
2 1664686 208390883 20
2 185647 691904720 21
2 562213100 573068873 22
4 12 50938831
2 2662035 500980836 23
3 872492511 1000000000 20
3 11358667 41952592 16
2 5046711 837157816 17
2 264532 973154193 18
2 200709821 190031430 19
4 16 14085687
2 984514216 233191253 20
2 9505217 268484090 21
2 9101110 720780107 22
4 12 42975444
2 9147013 713784174 23
2 6529258 439003119 24
2 970491 606257324 25
2 2496904 533000117 26
2 7497249 172862682 27
2 4009110 150270123 28
4 7 123373642
2 641660901 380580942 29
2 5082826 334621519 30
3 129661045 456965384 18
4 16 7321637
2 1442965 711459006 19
2 2786618 624365055 20
3 1 112439617 18
2 9636889 31458034 19
2 929094958 359666275 20
2 5532463 875333712 21
3 321676330 469745302 20
2 2496904 590374984 20
2 8395236 367036897 21
2 3882253 87533398 22
4 7 114522783
2 7423416 723593381 23
2 2093457 126393354 24
2 6196038 886744347 25
2 6711728 458266855 26
2 7497249 125486963 27
2 799807 924541728 28
2 2662035 899316796 28
2 6250776 277203205 29
2 8234865 899194090 30
2 5243046 353876091 31
2 3899975 161480200 32
2 8837540 128128673 33
4 19 23983084
2 4477483 414706204 34
3 955198310 1000000000 33
2 7017492 199138769 34
2 517288189 956303750 35
2 126127874 142332327 36
2 5082826 142489139 37
2 4843519 242061536 38
4 12 60830113
2 1998962 267682903 39
2 8609923 95536611 40
2 9809711 411201488 41
2 9716460 784705865 42
3 168195772 406053992 36
3 232258404 435705151 34
2 361869 102398678 35
2 3664594 36496823 36
2 9687619 13875540 37
2 792278960 361197501 38
2 4847401 716205762 39
2 347518 911448819 40
2 3484223 645130912 41
2 656188 452417753 42
2 9145733 862945902 43
2 7461610 98404591 44
2 847739 542591404 45
2 9658504 481967285 46
2 9654817 810659290 47
2 929094958 646677654 48
2 963264274 771714679 49
2 1074563 803631380 50
2 582645104 470155901 51
2 2758249 338510978 52
2 2612030 586189235 53
2 7451775 297717344 54
3 9220207 87533398 50
2 585392087 745026648 51
4 22 22686523
2 8601002 756470703 52
2 8532155 489246572 53
2 8069320 282443125 54
2 9335905 339382682 55
2 3737686 595423851 56
4 17 32592062
2 3899975 438135717 56
2 681025041 259822346 57
4 44 4185749
4 10 80970038
4 36 9234616
3 113763425 222847101 51
3 689242739 720498609 47
2 9981088 801141101 48
2 8438105 309286322 49
2 2024021 458570734 50
2 4987370 261335151 51
2 8467835 845588780 52
2 7284616 287650869 53
2 1513505 906100570 54
2 533176854 211851563 55
2 841207 476898808 56
3 41886595 251593873 52
2 3826544 244438013 53
3 232265996 511590060 34
2 8829077 78342974 35
2 2788794 398159487 36
2 7091595 329603836 37
2 7686232 585634501 38
2 832059185 607408554 39
2 8804582 667404859 40
2 639751 817327816 41
2 2596964 600198241 42
3 385314874 858302663 11
2 9717369 827879506 12
2 6799758 759505475 13
2 200709821 300701327 14
2 289271195 532184780 15
2 880680 571227477 16
2 54081 274396666 17
3 512486637 869784605 12
4 11 5348249
2 8945176 84892037 13
2 244465 417877866 14
2 4115622 660867835 15
3 467761436 641289309 15
2 4153171 782047268 16
2 8024192 838698829 17
3 830829212 908369743 11
3 499031416 602673623 11
2 7462993 598928458 12
2 8420230 163693659 13
2 1594151 96536680 14
2 9958020 400877441 15
2 6567981 122572406 16
2 974834 492664023 17
2 9319267 113693684 18
2 344144 975999453 19
4 11 55207170
2 6396039 996315208 20
2 288221668 449258977 21
2 8069320 136718861 22
3 33001932 485856345 9
2 9802789 427394062 10
2 8603786 206892047 11
2 358243099 976232012 12
2 111684136 545523925 13
2 3644993 418402682 14
2 6733238 710295243 15
2 6845975 396132120 16
3 416765659 656634915 11
2 1122064 53836445 12
3 269117484 364047397 12
3 83901304 320482405 11
2 517288189 526365345 11
2 2319693 862748438 12
2 2168978 277815031 13
2 2770714 501798019 14
2 1239631 818094576 15
2 7461610 514625036 16
2 8250088 425240981 17
2 6721921 160472890 18
3 581240549 988030063 9
2 6021234 41649751 10
2 7138659 583091060 11
2 5390032 941250909 12
4 7 81293041
2 5240071 102702536 13
2 3561060 900923233 14
2 7096717 859214550 15
2 8726610 45541303 16
2 2310467 101690708 17
2 5000496 666730429 18
2 9935401 989521602 19
4 12 40327676
2 5043012 599698881 20
2 7587565 137661366 21
2 6658866 521749271 22
2 1847715 991290676 23
2 7389200 80790045 24
2 9710473 18433442 25
3 651211373 1000000000 18
2 2266714 616259487 19
2 484210603 950675356 20
2 8465272 636221157 21
3 127652216 312984827 18
4 11 21912491
2 2801243 820424076 19
2 4374888 428747541 20
2 5973761 339507898 21
2 8657526 676729611 22
2 527575 300501080 23
3 783145927 1000000000 21
2 7618896 578677469 22
3 582588268 729338032 17
2 2938229 812775070 18
4 10 32615421
3 614311007 709654864 18
2 4051548 756542969 19
2 3900965 480854286 20
2 6818570 455729423 21
2 1748379 834611020 22
2 9013288 980356053 23
2 5137217 103628410 24
4 7 85194968
2 9061820 717684313 25
2 17669 984093678 26
2 5097066 683947119 27
2 535153019 755640108 28
2 5818760 59390517 29
2 445474209 667184474 30
2 356502 82104107 31
2 4580343 776141304 32
2 1902356 569819345 33
2 6460029 48643718 34
2 36896191 498327042 35
2 876478 139061043 36
2 8992639 482262496 37
2 612063484 717458713 38
2 4376773 34207150 39
2 3374122 670026031 40
2 2077883 112569580 41
2 5975624 132018421 42
2 9748193 273179930 43
2 1634390 393735147 44
2 8781111 383317432 45
2 1540308 346485649 46
4 26 11740309
2 4479259 255575756 47
4 16 39006818
2 9166846 102597107 48
2 8517823 3807136 49
3 976444765 1000000000 47
2 4280984 487434629 48
2 7451775 939213809 49
2 8799901 429213478 50
2 8965410 468265159 51
3 139439612 345193831 47
2 1366175 195271552 48
2 3472284 927030329 49
3 122697607 320772468 46
2 77377617 683910218 47
4 38 2396973
2 6618124 786449257 48
2 2807445 678946494 49
4 8 108762444
2 2020832 485829549 50
2 365202585 133141746 51
2 62533422 15203939 52
2 256614063 981793360 53
3 531758443 661020471 51
4 30 10307953
2 9524254 294700051 52
2 9269087 235246912 53
2 2054492 867120889 54
2 769317 646615566 55
2 3514890 129660943 56
2 344144 648338203 57
2 2020832 124779239 57
2 246133619 274303428 58
2 2096544 219440237 59
2 3983321 867230898 60
2 1506926 836309795 61
2 3826544 620486511 62
2 375547 36721196 63
2 1677576 572439861 64
2 6662817 419406938 65
4 32 12814688
3 66318299 503456463 36
3 3600695 34207150 32
2 7280643 339412884 33
2 6196038 317308912 34
2 3646092 777628905 35
3 883804136 1000000000 32
3 371405344 587562607 28
2 6310445 663045110 29
2 790002 396210263 30Editor is loading...