Untitled

 avatar
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