Untitled
unknown
plain_text
a year ago
8.4 kB
10
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