Untitled
unknown
plain_text
a year ago
19 kB
5
Indexable
----------------------MAIN---------------------------
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N, int mId[], int mNum[]);
extern int add(int mId, int mNum, int mParent);
extern int remove(int mId);
extern int distribute(int K);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_ADD 2
#define CMD_REMOVE 3
#define CMD_DISTRIBUTE 4
static bool run() {
int q;
scanf("%d", &q);
static int midArr[1000], mnumArr[1000];
int mid, mnum, mparent, n, k;
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], &mnumArr[j]);
}
init(n, midArr, mnumArr);
okay = true;
break;
case CMD_ADD:
scanf("%d %d %d %d", &mid, &mnum, &mparent, &ans);
ret = add(mid, mnum, mparent);
if (ans != ret)
okay = false;
break;
case CMD_REMOVE:
scanf("%d %d", &mid, &ans);
ret = remove(mid);
if (ans != ret)
okay = false;
break;
case CMD_DISTRIBUTE:
scanf("%d %d", &k, &ans);
ret = distribute(k);
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----------------------------
/*
* @file: [H2331] [Pro] 상품권배분
* @brief: 모범 답안
* @copyright: All rights reserved (c) 2023 Samsung Electronics, Inc.
*/
constexpr int MAX_NODE = 18000;
constexpr int HASH_SIZE = 30000;
struct Node {
Node* parent;
Node* child[3];
int num;
bool valid;
} NodePool[MAX_NODE];
int PoolCnt, GroupCnt;
struct HashNode {
int key;
Node* data;
} HashTbl[HASH_SIZE];
Node* hashFind(int key) {
unsigned long h = key % HASH_SIZE;
int cnt = HASH_SIZE;
while (HashTbl[h].key != 0 && cnt--) {
if (HashTbl[h].key == key) {
return HashTbl[h].data;
}
h = (h + 1) % HASH_SIZE;
}
return nullptr;
}
void hashAdd(int key, Node* data) {
unsigned long h = key % HASH_SIZE;
while (HashTbl[h].key != 0) {
if (HashTbl[h].key == key) {
HashTbl[h].data = data;
return;
}
h = (h + 1) % HASH_SIZE;
}
HashTbl[h].key = key;
HashTbl[h].data = data;
}
void delNode(Node* node) {
if (node == nullptr) return;
node->valid = false;
for (int i = 0; i < 3; ++i)
delNode(node->child[i]);
}
void init(int N, int mId[], int mNum[]) {
PoolCnt = 0;
for (int i = 0; i < HASH_SIZE; ++i) {
HashTbl[i].key = 0;
}
GroupCnt = N;
for (int i = 0; i < N; ++i) {
Node* node = &NodePool[PoolCnt++];
hashAdd(mId[i], node);
node->valid = true;
node->parent = nullptr;
node->child[0] = node->child[1] = node->child[2] = nullptr;
node->num = mNum[i];
}
}
int add(int mId, int mNum, int mParent) {
Node* node = &NodePool[PoolCnt++];
Node* parent = hashFind(mParent);
if (parent->child[0] == nullptr) {
parent->child[0] = node;
} else if (parent->child[1] == nullptr) {
parent->child[1] = node;
} else if (parent->child[2] == nullptr) {
parent->child[2] = node;
} else {
return -1;
}
Node* curr = parent;
while (curr) {
curr->num += mNum;
curr = curr->parent;
}
hashAdd(mId, node);
node->valid = true;
node->parent = parent;
node->child[0] = node->child[1] = node->child[2] = nullptr;
node->num = mNum;
return parent->num;
}
int remove(int mId) {
Node* node = hashFind(mId);
if (!node || !node->valid) {
return -1;
}
Node* parent = node->parent;
if (parent->child[0] == node) {
parent->child[0] = nullptr;
} else if (parent->child[1] == node) {
parent->child[1] = nullptr;
} else if (parent->child[2] == node) {
parent->child[2] = nullptr;
}
Node* curr = parent;
while (curr) {
curr->num -= node->num;
curr = curr->parent;
}
delNode(node);
return node->num;
}
int distribute(int K) {
int low = 1, high = 0;
for (int i = 0; i < GroupCnt; ++i) {
if (NodePool[i].num > high)
high = NodePool[i].num;
}
while (low <= high) {
int mid = (low + high) / 2;
int sum = 0;
for (int i = 0; i < GroupCnt; ++i) {
if (NodePool[i].num <= mid)
sum += NodePool[i].num;
else
sum += mid;
}
if (sum <= K) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
----------------------INPUT---------------------------
25 100
12
1 3
7 25
4 5
2 40
2 3 5 4 10
2 9 5 7 30
2 1 15 4 25
2 8 10 1 25
4 100 35
2 6 20 4 55
4 109 39
2 5 20 9 25
4 131 45
3 1 25
4 110 40
30
1 3
6932607 76
9283574 79
3799193 94
2 639546083 72 9283574 151
2 7490781 42 3799193 136
2 6568711 8 3799193 144
2 572001 54 7490781 96
2 3518315 8 7490781 104
2 2144677 10 3799193 216
2 2988431 28 9283574 179
2 5269673 6 3518315 14
4 463 208
2 2948033 98 6568711 106
2 973693771 88 2144677 98
4 551 296
2 5289891 12 5269673 18
2 6859805 6 5269673 24
2 4425671 76 973693771 164
2 339118881 86 5269673 110
2 6955307 44 5289891 56
3 973693771 164
4 666 411
2 231882 47 6859805 53
4 647 392
2 9653352 5 572001 59
2 9669600 9 6568711 115
3 5289891 56
2 106931781 50 5269673 195
2 9415005 2 9669600 11
3 6955307 -1
2 441886 51 339118881 137
2 2048342 75 441886 126
50
1 5
842745 82
5076024 77
8500675 48
5835274 11
8640445 62
2 4506471 64 8500675 112
2 7470401 90 5076024 167
2 8674635 60 5835274 71
4 490 163
2 2898467 44 8640445 106
2 2670877 70 7470401 160
2 2987079 36 4506471 100
2 3136289 14 5076024 251
2 4331691 56 2987079 92
2 9033317 50 3136289 64
2 5585359 84 9033317 134
2 7877097 10 4331691 66
2 2307507 68 4331691 134
2 958168877 30 5585359 114
2 9148119 84 9033317 248
2 706908721 6 4331691 140
2 4766523 88 2307507 156
2 3391221 74 5585359 188
2 601626335 100 9033317 422
4 1138 503
2 8648247 76 3391221 150
2 2536849 90 601626335 190
2 2727195 96 4331691 -1
2 5728981 38 601626335 228
2 4452159 72 8674635 132
2 1151321 2 706908721 8
2 7337251 92 2536849 182
4 1460 751
2 5553147 28 3391221 178
2 1452597 78 958168877 108
3 2536849 182
2 7346966 95 9148119 179
2 6891000 61 5553147 89
2 9865290 47 4766523 135
2 407564 17 6891000 78
2 2674110 39 4766523 174
2 5573344 37 5553147 143
2 4820824 61 9865290 108
4 1842 986
3 4452159 72
2 5770171 28 2898467 72
2 3991925 22 6891000 100
2 7363039 8 5835274 79
2 2772089 14 1452597 92
2 7391171 24 8640445 158
2 9064253 78 6891000 178
2 9785703 16 1452597 108
3 6891000 178
4 1672 828
100
1 10
364095 24
9369398 71
9703257 78
7834648 53
8930467 36
2908778 59
1373085 86
7485100 61
6813639 32
9353566 63
2 1317632 49 9353566 112
2 4324882 63 6813639 95
2 8923924 93 4324882 156
2 4541446 95 8923924 188
2 989800 45 9369398 116
2 4681914 27 1317632 76
2 3799292 65 4541446 160
2 7581102 59 6813639 407
4 932 280
2 2561766 67 1317632 143
2 1206856 69 1317632 212
4 980 233
2 6181056 97 1206856 166
2 2477394 91 4324882 407
2 627284 73 2477394 164
3 1206856 166
4 1278 559
2 558147431 64 2477394 228
2 2210369 82 989800 127
2 713547 4 3799292 69
2 3016965 2 2561766 69
4 1342 539
4 1197 394
4 1342 539
4 1197 394
2 3700021 6 2210369 88
2 7853983 76 989800 209
2 5532601 74 7485100 135
2 8548355 60 4681914 87
3 7581102 59
4 1536 517
2 7898344 5 1317632 210
2 2989754 39 713547 43
3 2477394 228
3 2210369 88
2 9835636 85 5532601 159
2 2548204 65 2989754 104
2 2394522 83 3016965 85
2 3924828 9 1373085 95
2 9595150 31 5532601 190
2 6452016 65 8548355 125
2 6441922 71 9835636 156
2 3839556 65 713547 173
4 1477 313
2 4905916 45 9835636 201
2 390382 11 6452016 76
4 1560 341
2 3746342 31 8548355 167
4 1586 349
2 9564510 83 9353566 546
2 1624064 73 9835636 274
2 4545912 93 3924828 102
2 5681520 5 7853983 81
2 4835714 63 2394522 146
2 3063556 41 5532601 420
2 3090678 19 2548204 84
2 1831640 17 3799292 274
2 6495312 1 3746342 32
3 2477394 -1
2 6902773 90 7898344 95
2 4503903 96 7898344 191
2 4588409 98 4835714 161
2 786676547 96 6495312 97
2 2038333 18 4545912 111
2 4937959 72 2548204 156
2 905537 6 4905916 51
2 4823627 24 6495312 121
4 2310 585
2 5238691 8 4905916 59
2 7754141 70 3839556 135
2 7697735 24 4588409 122
2 25614881 50 3090678 69
3 9564510 83
2 7197842 95 905537 101
2 2661524 81 6902773 171
2 8245510 75 3090678 144
2 83432 5 9703257 83
2 3069882 51 4823627 75
2 2814204 1 4905916 155
2 6370932 89 8930467 125
4 2665 663
3 4905916 155
2 2900615 64 2394522 332
4 2748 782
3 786676547 96
4 3001 994
2 147932 77 6902773 248
2 9653518 75 6495312 151
2 7026352 1 6902773 249
2 9217602 91 1624064 164
2 8128452 1 7754141 71
2 7130550 35 8128452 36
2 4434328 49 25614881 99
2 397635050 95 8548355 413
2 314175752 13 2548204 343
2 3635034 83 4545912 194
3 83432 5
2 9635319 96 9653518 171
2 7918033 2 9653518 173
400
1 40
5010705 10
4712624 21
8507291 88
5478978 43
5998293 26
998468 77
2775487 48
5895094 83
7008473 82
1165336 1
7779747 60
3742058 43
4298653 82
7844396 85
427077447 96
8852446 55
9590305 26
793216 61
4576683 80
5763730 55
9928037 74
2614164 89
1822287 60
2309126 3
7748073 54
3479016 89
137344307 12
9739834 51
495661 18
1016828 13
8021207 8
8566702 19
2284081 86
5590992 57
2981435 44
5469410 39
9124085 18
6730084 45
4962911 40
8435414 3
2 3389368 17 6730084 62
2 7862282 83 8566702 102
2 4330828 21 6730084 83
2 3040382 19 8435414 22
2 513696 89 1016828 102
2 4592946 11 4298653 93
2 1404724 1 9124085 19
2 4610598 43 3040382 62
2 2002056 53 3479016 142
2 90074 79 3040382 141
2 9573148 85 8566702 187
2 1414222 63 7779747 123
2 7489264 65 8435414 209
2 336384898 19 9739834 70
3 4592946 11
2 3134335 92 4330828 113
2 5653529 98 8566702 285
2 5084515 92 7489264 157
2 9310557 42 3134335 134
2 2379911 100 513696 189
2 2979041 50 2309126 53
2 8003819 76 2379911 176
2 9695269 30 3389368 47
2 3201295 88 4330828 243
2 3184937 86 3040382 227
2 9510515 36 7489264 193
2 1870829 14 3201295 102
2 6354455 68 3389368 115
2 391245681 94 2979041 144
2 7625339 92 2379911 268
2 6786259 56 9124085 75
2 461517 50 513696 407
3 3389368 115
2 3359054 99 5084515 191
2 5149168 93 998468 170
3 3040382 227
2 4014229 50 4962911 90
2 2443821 58 8003819 134
3 5149168 93
2 645236 69 6786259 125
3 3184937 -1
3 6354455 -1
2 9143112 9 4298653 91
2 2076186 31 336384898 50
3 6786259 125
2 9024183 96 9143112 105
2 5732751 24 5653529 122
2 432501673 98 2443821 156
2 3458291 44 336384898 94
2 1087085 2 1165336 3
2 9335063 72 9310557 114
2 9714543 24 1016828 600
2 4778121 38 9739834 183
2 8544723 8 9143112 113
2 6719181 14 3359054 113
2 8963173 82 1404724 83
2 3533647 92 2002056 145
2 2335923 24 4576683 104
2 9068057 98 9573148 183
2 530863 12 9714543 36
2 192207561 62 8544723 70
2 8050529 14 7625339 106
2 6968043 52 391245681 146
2 9565861 14 8544723 84
2 7688381 66 8852446 121
2 4063591 96 530863 108
2 116514625 2 6968043 54
2 4785867 20 8003819 252
2 9794595 56 998468 133
3 2979041 198
4 4146 394
2 8314274 35 2335923 59
2 6193956 1 6719181 15
3 6193956 1
2 163641 2 9565861 16
3 9143112 191
2 2951152 97 336384898 191
4 4183 476
2 2971240 69 8003819 321
2 2070368 49 3134335 255
2 1241458 87 7688381 153
2 2869620 77 3533647 169
3 4610598 -1
2 7824073 78 137344307 90
2 5319519 76 9310557 190
2 92358009 86 2379911 613
2 9097027 88 9794595 144
2 790589 70 9097027 158
2 7084245 66 793216 127
2 9870143 24 7824073 102
2 640345 34 5478978 77
2 7588003 48 5469410 87
2 4993821 6 432501673 104
2 5684021 2 92358009 88
2 8339103 100 432501673 204
2 9335609 34 530863 142
2 4521041 14 4993821 20
2 7006427 92 5732751 116
2 143795 32 9714543 198
2 4700461 6 5732751 122
2 7951575 24 461517 74
2 352817 50 4063591 146
2 4763323 88 530863 280
2 2694291 24 1241458 111
2 2277687 48 461517 122
2 5378705 98 7862282 181
2 9649435 100 7006427 192
3 9510515 36
2 7514180 73 9794595 287
2 3336118 87 9870143 111
2 3259800 33 3533647 202
2 6862736 1 8507291 89
2 9491874 55 9714543 391
2 342820 77 1087085 79
2 4926742 51 1414222 114
2 9787896 49 3458291 93
2 4705226 55 4778121 93
2 2604172 53 7688381 230
2 6450308 45 9794595 332
2 3705974 7 6450308 52
3 4014229 50
2 6599473 78 5319519 154
2 378567995 52 3458291 145
2 879733 34 9870143 145
2 8456543 96 7514180 169
2 591667833 22 8339103 122
2 7637915 36 3705974 43
2 5863253 54 2971240 123
2 847045183 44 432501673 284
2 8792921 14 7084245 80
2 7106161 94 4785867 114
2 819835 32 591667833 54
3 8792921 14
2 4329818 3 5084515 208
2 8925596 17 9335609 51
2 1637838 95 7688381 325
2 194994032 53 2951152 150
2 4037378 95 4521041 109
3 8050529 14
2 909951 76 8963173 158
2 703365529 66 3705974 109
3 1087085 79
2 7055274 71 4778121 164
2 504696172 9 4521041 118
2 6368286 23 4700461 29
2 3171776 81 4330828 613
3 7951575 24
3 4705226 55
2 1769044 65 4778121 174
2 3557830 99 1637838 194
2 1337982 95 9590305 121
3 194994032 53
2 8010775 36 143795 68
2 486276721 26 1241458 137
2 2354683 32 1016828 1747
2 9207605 42 137344307 277
2 5274573 42 7106161 136
2 4576997 22 8314274 57
2 186959 68 1769044 133
3 5863253 54
2 4397758 95 9491874 150
2 8085088 89 1637838 283
3 9794595 537
2 9590755 100 92358009 188
2 6380381 46 9335609 97
2 2376327 100 6368286 123
2 7307871 44 4926742 95
2 2815737 34 6368286 157
2 3004867 64 4785867 220
2 1135805 6 5378705 104
2 6260199 64 4576997 86
2 2287553 10 486276721 36
3 9207605 42
2 672690 91 8010775 127
2 1815274 55 186959 123
2 3478444 69 847045183 113
2 4543070 39 3336118 126
2 7988992 85 8339103 239
3 186959 123
2 507621 22 7625339 114
2 257615 32 879733 66
3 6599473 78
2 3763390 27 6862736 28
3 8339103 239
3 2694291 24
2 8623448 5 2443821 398
2 681770 95 640345 129
2 2647148 45 2775487 93
2 8123934 7 2647148 52
2 7834816 57 4397758 152
2 9826770 95 9124085 272
2 5737098 79 6862736 107
2 41932 77 257615 109
4 6878 743
2 8420986 3 4763323 91
3 4592946 -1
2 152599 28 5469410 115
2 6439025 90 3478444 159
2 9136507 24 879733 167
3 2376327 100
2 8714660 37 4329818 40
2 2597398 75 8085088 164
2 1916920 73 41932 150
2 1880138 27 378567995 79
2 5578508 25 9491874 232
2 5777086 43 5274573 85
2 789856 89 3478444 248
2 6223730 27 3171776 108
2 7153780 49 6380381 95
2 3614694 3 672690 94
2 4008790 47 1916920 120
3 7834816 57
2 8657219 36 4763323 127
2 8111293 10 1880138 37
2 4791271 12 7779747 230
2 2606145 78 7307871 122
2 5457625 10 1337982 105
2 620579 8 6730084 615
2 559901 34 7307871 156
2 56065619 48 1637838 406
2 654577229 90 5469410 205
2 5955831 12 3259800 45
3 681770 95
2 7909360 69 3171776 177
2 5657602 43 1337982 148
2 685572 37 6380381 132
2 6918902 23 6223730 50
2 5174232 53 352817 103
2 8860586 7 3259800 52
2 700908 29 879733 316
2 448481950 11 2647148 63
2 9217600 1 1916920 121
2 229634616 5 8010775 135
2 1375754 47 1916920 168
2 798970188 29 6380381 161
2 4742980 85 789856 174
2 270902 83 9217600 84
2 483383320 49 3171776 249
2 8537322 19 7055274 90
2 6865964 17 1769044 82
2 9771870 63 41932 391
2 8446208 81 6862736 188
2 6544274 3 3336118 129
2 6689940 69 3004867 133
2 5749004 81 8111293 91
3 6862736 188
2 2045569 90 4791271 102
2 5029131 100 2951152 197
2 7818565 22 8010775 157
2 1576495 8 1337982 156
2 8758985 30 1135805 36
2 7953939 40 483383320 89
2 306108557 10 507621 32
3 5578508 25
2 173966 55 1880138 173
2 3461680 25 5955831 37
2 9331906 43 229634616 48
3 879733 510
2 839964991 96 3557830 195
2 4582489 14 1769044 96
2 4926705 86 7779747 518
2 2619899 32 8758985 62
2 7191713 30 672690 124
2 5901611 80 9310557 270
2 619915237 70 4926742 277
2 8824061 6 2070368 55
2 5677351 8 8758985 70
2 4519809 54 8860586 61
2 627353 2 6865964 19
2 5886691 8 4778121 234
2 7075293 94 789856 268
2 7485941 26 620579 34
2 4469727 68 7818565 90
2 3951653 22 3461680 47
2 4816829 50 6368286 107
2 8588391 28 1165336 29
2 197057 26 152599 54
2 6175383 56 6223730 106
2 2620657 14 8420986 17
2 4895483 92 7485941 118
2 8244051 28 197057 54
2 1560781 66 5174232 119
2 375535863 12 56065619 60
2 2038609 14 2309126 17
2 5338345 22 7191713 52
2 962010163 8 3461680 55
2 7122989 82 4962911 122
2 418903 24 7485941 142
2 2817201 74 5338345 96
2 2295739 4 6865964 23
2 118753 90 7824073 321
2 2998777 46 1769044 148
2 2167313 30 7075293 124
2 9306651 68 5955831 135
2 9011285 22 8435414 335
2 8295871 8 152599 90
2 7160537 98 8657219 134
2 1755505 6 8925596 23
2 4978939 48 8714660 85
2 1270965 58 685572 95
4 11143 2955
2 8768299 20 9491874 170
2 2058085 70 2647148 133
2 1359439 24 559901 58
2 6530281 14 685572 109
2 9178753 94 3614694 97
2 7561227 36 7191713 162
2 9648709 30 4298653 112
4 10480 2168
2 9132253 58 6223730 164
2 7976199 32 685572 141
4 9848 1478
2 2351455 68 4926705 154
2 4986105 18 9335609 340
2 2933009 90 8111293 181
2 7007515 96 3951653 118
3 8768299 20
2 7184196 97 2443821 883
2 5981750 11 2998777 57
2 3529140 21 448481950 32
2 6021158 71 6439025 161
2 192264 5 7953939 45
2 909452800 5 8657219 139
2 2934862 71 1404724 230
2 401344780 81 9306651 149
2 9387710 75 7055274 165
3 4926705 154
2 8905739 92 2076186 123
2 959384773 10 7976199 42
2 6332381 38 6689940 107
3 685572 151
2 6750622 47 2934862 118
2 7561280 49 3529140 70
2 4385720 17 962010163 25
2 8486576 49 1560781 115
3 8792921 -1
2 7112661 38 5274573 123
2 4568895 40 4385720 57
2 8498137 6 627353 8
3 1880138 263
2 3333226 3 7485941 145
2 5847468 45 9331906 88
2 3861156 5 2058085 75
2 1661206 99 654577229 189
2 4097614 47 8537322 66
2 2892400 5 306108557 15
2 576607618 83 559901 141
4 10634 1675
2 9485370 39 2045569 129
4 11175 2177
2 3897304 57 7006427 249
2 8741930 3 8295871 11
2 8673388 61 620579 214
2 4233886 35 448481950 116
2 9199040 81 3529140 151
2 2730936 69 1576495 77
2 406410 3 7184196 100
2 9465036 37 1135805 113
2 9605152 53 401344780 134
2 8745880 57 9573148 240
2 151531754 15 7075293 139
2 1280044 37 2620657 51
2 2473054 83 9465036 120
2 597888 21 118753 111
3 6439025 161
2 7719171 48 4962911 170
2 4626173 90 2620657 141
4 12889 3286
2 2643221 10 839964991 106
3 4926705 -1
2 2969974 95 2038609 109
2 5802584 49 9648709 79
2 2490538 63 6260199 127
2 4067938 7 909452800 12
2 2131812 21 8537322 87
2 7218262 51 9387710 126
3 229634616 93
2 2559683 100 8244051 128
2 3612477 34 576607618 117
2 51848295 12 5457625 22
2 1995073 6 5457625 28
2 6418009 30 7191713 192
2 9073571 12 6689940 119
2 987610141 90 2473054 173
3 9387710 126
2 3218270 67 7184196 167
3 9306651 202
2 8304683 80 8905739 172
2 477819109 46 7184196 213
2 763422287 28 4763323 406
3 7834816 -1
2 162280 81 6544274 84
2 4746426 59 7160537 157
2 748191612 61 6750622 108
2 8193706 3 597888 24
2 5300076 29 378567995 81
2 7097758 59 7561280 108
2 3040832 85 7153780 134
2 8843090 27 4233886 62