Untitled
plain_text
a month ago
13 kB
10
Indexable
Never
--------------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------------------ #define MAX_NODE 18001 #define HASH_SIZE 36001 using namespace std; struct Node { int mId; Node* parent; Node* child[3]; int num; int hashNext; bool valid; Node(){ parent = nullptr; for(int i = 0; i < 3; i++) child[i] = nullptr; num = 0; hashNext = -1; valid = false; } bool addChild(Node* n){ for(int i = 0; i < 3; i++){ if(child[i] == nullptr){ child[i] = n; return true; } } return false; } void removeChild(Node* n){ for(int i = 0; i < 3; i++){ if(child[i] == n){ child[i] = nullptr; } } } }departments[MAX_NODE]; int departmentCnt, groupCnt; int hashTb[HASH_SIZE]; void addHash(int id) { int h = departments[id].mId % HASH_SIZE; departments[id].hashNext = hashTb[h]; hashTb[h] = id; } int getHash(int mId) { int h = mId % HASH_SIZE; int id = hashTb[h]; while(id != -1 && departments[id].mId != mId){ id = departments[id].hashNext; } return id; } void init(int N, int mId[], int mNum[]) { departmentCnt = 0; for(int i = 0; i < HASH_SIZE; i++){ hashTb[i] = -1; } for(int i = 0; i < MAX_NODE; i++){ departments[i] = Node(); } groupCnt = N; for (int i = 0; i < N; ++i) { Node* node = &departments[departmentCnt]; node->valid = true; node->num = mNum[i]; node->mId = mId[i]; addHash(departmentCnt); departmentCnt++; } } int add(int mId, int mNum, int mParent) { int idParent = getHash(mParent); Node* node = &departments[departmentCnt]; Node* parent = &departments[idParent]; if(!parent->addChild(node)) return -1; Node* curr = parent; while (curr) { curr->num += mNum; curr = curr->parent; } node->mId = mId; node->valid = true; node->parent = parent; node->num = mNum; addHash(departmentCnt); departmentCnt++; return parent->num; } int remove(int mId) { int idx = getHash(mId); if(idx == -1) return -1; Node* node = &departments[idx]; if (!node || !node->valid) { return -1; } Node* parent = node->parent; Node* curr = parent; while (curr) { if (!curr->valid){ node->valid = false; return -1; } curr->num -= node->num; curr = curr->parent; } node->valid = false; parent->removeChild(node); return node->num; } int distribute(int K) { int low = 1, high = 0; for (int i = 0; i < groupCnt; ++i) { if (departments[i].num > high) high = departments[i].num; } while (low <= high) { int mid = (low + high) / 2; int sum = 0; for (int i = 0; i < groupCnt; ++i) { if (departments[i].num <= mid) sum += departments[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 200 1 20 7411184 33 237531 20 9321858 95 9851157 70 124082308 13 7105279 80 5592310 87 5292953 82 8115416 53 2361827 40 5554474 51 9647197 98 3023340 77 1054599 8 625998366 31 4425313 2 5964864 25 9305579 80 5232978 3 2310693 26 2 4702735 24 5964864 49 2 6239657 58 9647197 156 2 437235 60 237531 80 2 6740461 78 625998366 109 2 7451927 88 5292953 170 2 5055729 78 437235 138 4 1265 129 2 6637577 38 5055729 116 2 8096339 28 2310693 54 2 5625037 58 9305579 138 2 7646967 60 4702735 84 2 8343249 18 5554474 69 2 624842843 40 7451927 128 2 5023125 46 437235 222 2 9126911 8 5964864 117 2 6758169 94 624842843 134 2 981212259 64 9851157 134 3 8343249 18 2 1328492 93 6239657 151 3 1328492 93 2 6536545 26 4425313 28 2 3056761 86 437235 308 2 5581073 90 6637577 128 3 1328492 -1 2 5929154 31 624842843 165 2 4318916 45 3056761 131 2 5405238 51 7451927 304 2 1056280 81 3056761 212 4 1809 266 4 2030 377 4 1986 355 3 5055729 206 2 4713287 60 2361827 100 2 6920097 18 9851157 152 3 8343249 -1 3 6740461 78 2 4631939 52 5625037 110 2 1662717 26 9647197 182 2 9847079 56 5023125 102 2 267465985 42 9851157 194 2 541765145 90 8096339 118 2 8262627 32 9847079 88 2 4032861 70 6758169 164 3 5405238 51 3 6536545 26 2 3428577 14 5625037 124 2 7399417 74 9847079 162 2 304195 52 9847079 214 2 8436123 36 1054599 44 2 595669 6 5292953 411 3 6758169 164 2 1213500 65 624842843 136 2 8199534 15 5232978 18 2 886597008 13 624842843 149 2 9715490 43 5625037 167 2 1651418 67 9126911 75 2 1797138 43 267465985 85 4 2147 238 3 8262627 32 2 1763965 38 4631939 90 2 5744935 8 5929154 39 4 2441 392 2 5853439 88 5744935 96 2 8946647 44 541765145 134 2 1594289 74 3056761 286 4 2470 355 4 2748 567 2 2862197 10 1651418 77 2 1348063 84 1662717 110 2 7371129 14 2862197 24 2 8196291 68 5929154 195 4 2804 468 2 8138139 60 7105279 140 2 2024021 94 7399417 168 2 36896191 16 4318916 61 2 4842841 94 8436123 130 2 1870883 44 7399417 212 2 3032187 60 541765145 194 2 4648117 38 1056280 119 4 2854 386 2 5720013 42 7399417 254 2 5042551 4 1763965 42 2 6433489 94 5929154 289 2 6328411 68 8946647 112 2 9903253 54 3032187 114 2 7530367 24 5720013 66 2 24857 86 8436123 216 2 8390883 76 9847079 462 3 5853439 88 2 562213100 73 24857 159 4 3715 853 2 980836 81 6920097 99 3 4318916 61 4 3468 525 2 5046711 16 5964864 224 2 3154193 46 6433489 140 2 9530395 80 5046711 96 2 3191253 26 886597008 39 2 7260351 20 8946647 132 2 257541593 10 9126911 109 2 8784931 84 3056761 363 2 2919069 66 1651418 157 4 4034 827 2 3000117 18 8138139 78 2 6992031 60 304195 112 2 1043191 96 541765145 432 2 2773969 26 5720013 92 2 3881435 100 4842841 194 4 4414 993 2 7909939 32 8138139 110 2 1263405 30 8946647 162 2 8438103 20 5042551 24 4 3769 449 2 831581 42 1056280 161 2 2135303 84 3032187 198 2 7036897 2 3881435 102 4 4155 583 2 9305849 50 1263405 80 2 2093457 54 3000117 72 2 6744347 52 6328411 120 2 406101 14 24857 173 2 799807 28 8196291 96 2 967329113 46 1797138 89 2 8873635 76 1797138 165 2 2047389 46 8784931 130 4 4883 974 2 418347829 58 8196291 154 2 580689439 32 6328411 152 2 6844089 46 1054599 459 2 4248451 92 8115416 145 2 517288189 50 5046711 146 3 8873635 76 2 8815294 39 6844089 85 2 2061536 97 5744935 105 2 1998962 3 2093457 57 2 9020916 69 9321858 164 3 3428577 14 2 4705865 90 3154193 136 2 9750497 38 7260351 58 2 5111801 94 831581 136 2 9687619 40 1043191 136 2 1197501 26 8138139 193 2 3807335 36 2093457 93 2 5091649 34 1662717 144 2 2417753 74 1662717 218 2 7493923 100 4842841 296 2 847739 4 5042551 28 2 1967285 66 8815294 105 2 6895135 8 9903253 62 4 5255 698 2 1714679 56 4648117 94 2 9933009 66 9750497 104 4 5978 1091 2 2758249 78 7260351 202 2 6189235 60 562213100 133 2 1851147 76 580689439 108 2 3235397 10 7371129 24 2 6470703 64 5720013 156 2 3810121 82 1197501 108 2 1318547 20 5046711 166 2 5423851 100 2024021 194 4 5522 729 2 8151619 92 1851147 168 2 3516093 82 6470703 146 4 6076 951 3 6470703 146 2 7559620 73 1998962 76 3 2135303 84 2 8438105 22 9305849 72 2 2723 36 580689439 236 2 6295453 62 831581 198 2 5098311 16 967329113 62 2 1513505 70 406101 84 2 1851563 56 1043191 192 2 1886595 28 2919069 94 2 4438013 86 6189235 146 2 9779879 24 2758249 102 2 6551553 94 1318547 114 3 1851563 56 2 8134514 47 1513505 117 2 7796 85 8390883 161 2 8804582 59 4713287 119 2 7327816 49 2361827 208 2 648986 55 6992031 115 2 1410908 69 3000117 253 2 6799758 75 8151619 167 2 6052294 95 625998366 126 3 2758249 102 2 9192947 16 9903253 78 3 6744347 52 2 824965820 65 1886595 93 2 7249262 63 5592310 150 2 2556944 17 6799758 92 2 4065186 23 2773969 49 2 2047268 9 3810121 91 3 6470703 -1 2 3844281 90 8815294 195 3 4842841 296 2 598928458 59 3807335 95