Untitled
unknown
plain_text
a year ago
8.4 kB
9
Indexable
//input 25 100 26 100 21 7 3 8 19 18 9 18 19 2 1 4 1 16 18 2 7 0 6 9 2 11 18 1 2 0 2 1 0 2 0 1 2 2 0 0 1 1 1 1 0 1 0 1 0 500 2 75 500 2 73 500 2 68 300 2 796 814 400 0 -686 -5394 500 1 -1330 300 17 -275 -273 300 11 364 -304 300 14 -76 -76 500 2 -2667 300 9 -172 -171 300 1 -970 -1637 300 11 207 -97 500 1 -1804 300 16 -690 -1367 400 2 471 3029 400 1 -649 -5498 500 2 -2677 500 2 -4310 500 2 -4707 300 2 -890 395 500 1 -2082 300 20 139 -546 400 2 59 2434 300 9 -589 -230 27 100 24 8 3 0 2 10 2 13 1 1 23 14 17 11 15 21 19 18 21 6 6 12 20 2 10 10 17 0 0 1 2 1 0 1 0 0 0 1 1 2 2 0 0 2 2 2 1 2 1 0 0 500 3 152 400 0 -493 -4807 500 1 -949 300 18 -197 -185 500 3 -2541 300 18 -583 -768 300 16 818 824 300 21 695 705 500 2 -181 300 18 337 -431 300 2 199 209 500 3 -2734 300 10 753 764 500 1 -886 300 2 404 613 300 23 -761 -1237 400 0 294 -2628 500 1 -586 400 1 -747 -3098 500 1 -1650 500 2 -2697 500 1 -1100 300 19 -192 -919 300 4 828 94 400 0 773 5102 300 21 690 648 29 100 27 9 3 26 9 8 14 19 7 14 15 3 15 23 25 9 11 5 26 14 3 23 21 5 5 19 5 1 13 21 0 1 0 2 1 2 1 0 2 2 2 0 1 1 2 1 0 0 2 2 2 1 2 0 0 0 1 300 23 257 262 500 4 471 500 4 464 500 3 167 500 4 223 400 0 759 7198 500 4 4764 300 24 -397 363 300 16 871 1644 300 2 140 907 300 8 202 205 300 22 456 475 300 14 797 802 500 3 4454 500 2 2471 500 4 4299 300 11 -255 529 300 21 -449 -444 300 11 -996 -467 400 2 -409 -2500 300 21 136 -308 400 0 124 7677 400 2 637 3870 300 23 116 1261 500 1 832 300 7 -362 536 500 2 2869 300 25 -823 73 41 100 30 10 1 14 12 22 14 27 16 3 19 19 13 23 5 29 5 9 14 16 0 8 13 27 19 6 14 3 11 16 13 15 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 500 2 118 400 0 973 29601 400 0 -760 6801 400 0 -383 -4689 500 4 -2504 300 27 107 -50 400 0 -632 -23542 400 0 340 -13342 400 0 850 12158 400 0 117 15668 300 14 -172 342 400 0 849 40966 300 26 369 1739 300 29 178 1538 500 4 22529 400 0 365 52463 500 2 14027 300 10 871 2613 500 1 6938 300 26 -519 1585 300 14 -653 903 500 1 6786 400 0 -976 22882 400 0 -978 -6458 300 6 -270 -502 400 0 -509 -21998 300 15 -300 -1030 500 4 -12121 400 0 54 -20678 300 26 -907 -1731 300 11 919 234 300 2 -103 -771 400 0 14 -20349 500 5 -12433 500 1 -1750 300 27 -160 -716 400 0 411 -8179 300 13 -168 -428 500 5 -5264 300 18 899 642 49 100 50 10 2 27 25 4 39 28 10 41 28 27 25 10 6 36 2 3 35 40 28 44 5 28 17 15 20 16 22 26 20 9 7 20 19 44 22 12 15 9 37 2 0 32 31 8 27 49 30 7 31 1 48 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 1 300 49 318 366 300 8 -26 1 300 33 -93 -71 500 1 421 300 43 -796 -769 400 1 -780 -25568 500 2 -5963 300 46 274 281 400 1 752 -752 300 2 990 994 400 0 -610 -8788 300 19 -58 -81 300 13 -516 -1124 300 21 -33 -44 300 9 -804 -807 400 1 -929 -32304 400 1 -974 -64446 500 4 -47770 300 38 306 -302 400 1 -352 -76062 400 0 -424 -16206 500 5 -76003 300 15 203 -2045 400 1 -385 -88564 400 0 -145 -18671 300 29 491 -2170 500 4 -71084 300 3 333 -2296 500 1 -16244 500 1 -16707 300 45 -738 -3376 400 1 -253 -96827 300 3 -722 -3271 400 0 400 -11871 300 43 42 -3648 500 3 -56799 300 29 510 -1913 500 2 -38349 400 0 470 -3881 300 22 710 -2196 300 48 -57 -2977 300 32 281 16 300 38 -71 -72 300 24 -188 -481 400 1 -52 -98060 300 11 -175 -478 300 15 -757 -3492 500 5 -85978 //#ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> #define CMD_INIT 100 #define CMD_DESTROY 200 #define CMD_UPDATE 300 #define CMD_UPDATE_JOB 400 #define CMD_MOVE 500 ///////////////////////////////////////////////////////////////////////// extern void init(int N, int M, int J, int mPoint[], int mJobID[]); extern void destroy(); extern int update(int mID, int mPoint); extern int updateByJob(int mJobID, int mPoint); extern int move(int mNum); ///////////////////////////////////////////////////////////////////////// #define MAX_N 100000 static int Point[MAX_N]; static int JobID[MAX_N]; static int run() { int isOK = 0; int N; int cmd,result, check; int mN,mM,mJ; int mID,mJobID; int mPoint,mNum; scanf("%d", &N); for (int c = 0; c < N; ++c) { scanf("%d", &cmd); switch (cmd) { case CMD_INIT: scanf("%d %d %d", &mN, &mM, &mJ); for (int i = 0; i < mN; i++) scanf("%d", &Point[i]); for (int i = 0; i < mN; i++) scanf("%d", &JobID[i]); init(mN, mM, mJ, Point, JobID); isOK = 1; break; case CMD_UPDATE: scanf("%d %d", &mID, &mPoint); result = update(mID, mPoint); scanf("%d", &check); if (result != check) isOK = 0; break; case CMD_UPDATE_JOB: scanf("%d %d", &mJobID, &mPoint); result = updateByJob(mJobID, mPoint); scanf("%d", &check); if (result != check) isOK = 0; break; case CMD_MOVE: scanf("%d", &mNum); result = move(mNum); scanf("%d", &check); if (result != check) isOK = 0; break; default: isOK = 0; break; } } destroy(); return isOK; } int main() { setbuf(stdout, NULL); freopen("input.txt", "r", stdin); int T, MARK; scanf("%d %d", &T, &MARK); for (int tc = 1; tc <= T; tc++) { if (run()) printf("#%d %d\n", tc, MARK); else printf("#%d %d\n", tc, 0); } return 0; } // #include<iostream> #include<vector> #include<map> #include<queue> #include<set> using namespace std; struct Passenger { int ID; mutable int Point; int JobID; int trainID; }; struct pointCompare { public: bool operator() (Passenger *p1, Passenger *p2) { if(p1->Point == p2->Point) return p1->ID > p2->ID; //neu bang diem thi lay min id return p1->Point < p2->Point; //lay max diem } }; vector<Passenger*> User; vector<vector<Passenger*>> JOB; vector<multiset<Passenger*, pointCompare>> Train; //heap void init(int N, int M, int J, int mPoint[], int mJobID[]) { User.clear(); User.resize(N); JOB.clear(); JOB.resize(J); Train.clear(); Train.resize(N/M, multiset<Passenger*, pointCompare>()); int m = 0; for (int i = 0; i < N; i++) { m = i/M; Passenger * new_user = new Passenger(); new_user->ID = i; new_user->Point = mPoint[i]; new_user->JobID = mJobID[i]; new_user->trainID = m; User[i] = new_user; JOB[mJobID[i]].push_back(new_user); Train[m].insert(new_user); } } void destroy() { } int update(int mID, int mPoint) { //Tim xong xoa trong tree Train[User[mID]->trainID].erase(User[mID]); //Update diem User[mID]->Point += mPoint; //Add vao tree Train[User[mID]->trainID].insert(User[mID]); //Tra ve diem cua khach hang co mID return User[mID]->Point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (unsigned int i = 0; i < JOB[mJobID].size(); i++) { //Tim xong xoa trong tree Train[JOB[mJobID][i]->trainID].erase(JOB[mJobID][i]); //Cap nhat diem JOB[mJobID][i]->Point += mPoint; //Add vao tree node vua update Train[JOB[mJobID][i]->trainID].insert(JOB[mJobID][i]); //Cap nhat tong diem cua tat ca job co mJobID sum +=JOB[mJobID][i]->Point; } return sum; } int move(int mNum) { int count = 0; int num_train = Train.size(); vector<vector<Passenger*>> before(num_train, vector<Passenger*>(mNum)); vector<vector<Passenger*>> after(num_train, vector<Passenger*>(mNum)); multiset<Passenger*, pointCompare>::iterator iter = Train[0].begin(); for (int i = 0; i < mNum; i++) { after[0][i] = *iter; count += after[0][i]->Point; ++iter; } for (unsigned int i = 1; i < num_train; i++) { auto iter1 = Train[i].rbegin(); for (int j = 0; j < mNum; j++) { before[i][j] = *iter1; count += before[i][j]->Point; ++iter1; } if(i<num_train-1){ multiset<Passenger*, pointCompare>::iterator iter2 = Train[i].begin(); for (int j = 0; j < mNum; j++) { after[i][j] = *iter2; count += after[i][j]->Point; ++iter2; } } for (int j = 0; j < mNum; j++) { after[i-1][j]->trainID += 1; before[i][j]->trainID -= 1; Train[i].insert(after[i-1][j]); Train[i-1].insert(before[i][j]); Train[i-1].erase(after[i-1][j]); Train[i].erase(before[i][j]); } } return count; }
Editor is loading...
Leave a Comment