Untitled
unknownplain_text
2 months ago
14 kB
2
Indexable
Never
[Problem Description]
The last bastion of humanity – < Survival Train >
The extreme weather condition froze everything on the Earth. One train is relentlessly travelling.
Humanity’s last survivors are on the train.
The train is far from upholding equality. The tail section of the train is where cold, hunger, and dirt prevail while the head car is of comfort and luxury.
The closer to the head of train, the better the condition.
All passengers hope to move car-by-car up toward the front of the train.
In order to go there, there is no other way but to save money diligently.
N passengers are aboard. There are M passengers each in N/M train sections. (N is a multiple of M).
Each passenger will receive their own Passenger ID whose value is from 0 to N-1.
In the very first train section, Passenger IDs from 0 to M-1 are aboard.
In the second train section, Passenger IDs from M to 2M-1 are aboard.
Like the order above, passengers are aboard until the last section, the tail section of the train.
All passengers have jobs and accounts managing points that are used like money.
Points earned individually and through one’s job and points that have to be paid are calculated and reflected in the passengers’ accounts frequently.
Passengers with many points move up toward the section in front while passengers with few points move back to the section behind.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.
The following is the description of API to be written in the User Code.
void init(int N, int M, int J, int mPoint[], int mJobID[])
This function is called in the beginning of each test case.
There are N passengers. In a group of M, each group is aboard in N / M sections. N is a multiple of M.
Passenger ID is given in order from 0 to N-1. Starting from passengers with small ID value, M passengers each get on to the front part of the train.
mPoint[] is the number of points possessed by a passenger. mJobID[] is the job of a passenger.
There are J types of job. Job ID is from 0 to J-1.
The information of Passenger ID 0 are mPoint[0] and mJobID[0]. The information of Passenger ID 1 are mPoint[1] and mJobID[1]. The information of passengers until Passenger ID N-1 are given in order.
The maximum number of people by job does NOT exceed 200.
__Parameters
_____N : The number of passengers (21 ≤ N ≤ 100,000)
_____M : The number of passengers in one section (7 ≤ M ≤ 10,000 and 2 ≤ N / M ≤ 10)
_____J : The number of types of job (1 ≤ J ≤ 1000)
_____mPoint : The number of points possessed by each passenger ( 0 ≤ mPoint[] ≤ 10,000)
_____mJobID : The Job ID of passenger (0 ≤ mJobID[] ≤ J - 1)
void destroy()
This function is called at the end of each test case.
Even if the function is left empty, this does not affect the grading.
int update(int mID, int mPoint)
This function reflects mPoint in the account of the passenger whose ID is mID.
When mPoint is a positive number, it means that the number of the passenger’s points increased. When it is a negative number, it means that the number of the points decreased.
After reflecting the number of points, this function returns the number of the passenger’s points whose ID is mID.
It is guaranteed that the number of points possessed by Passenger mID is within the range of -1,000,000,000 to 1,000,000,000.
__Parameters
_____mID : The Passenger ID (0 ≤ mID ≤ N-1)
_____mPoint : The number of points reflected in an account ( -1,000 ≤ mPoint ≤ 1,000 )
__Returns
_____The point earned by a passenger
int updateByJob(int mJobID, int mPoint)
This function reflects mPoint in accounts of all passengers whose Job ID is mJobID.
When mPoint is a positive number, it means that the number of the passenger’s points increased. When it is a negative number, it means that the number of points decreased.
After reflecting the number of points, this function returns the sum of points possessed by passengers whose Job ID is mJobID.
It is guaranteed that the sum of points possessed by passengers whose Job ID is mJobID is within the range of -1,000,000,000 to 1,000,000,000.
__Parameters
_____mJobID : The Job ID (0 ≤ mJobID ≤ J - 1)
_____mPoint : The number of points reflected in an account ( -1,000 ≤ mPoint ≤ 1,000 )
__Returns
_____ The sum of points possessed by passengers whose Job ID is mJobID
int move(int mNum)
From the biggest points to the smallest points by train section, this function selects the top mNum and bottom mNum passengers.
When the number of points is the same, the passenger whose ID is smaller is ranked higher.
As there are no train section in front of the very first section, this function does NOT select the top mNum passengers.
As there are no train section behind the tail section, this function does NOT select the bottom mNum passengers.
After the selection, the top nNum passengers in each section move to the section in front, while the bottom nNum passengers in each section move to the section behind.
This function returns the sum of points possessed by the passengers who moved.
When selecting the top mNum and bottom mNum passengers in one section, there is NO case when the passengers overlap.
It is guaranteed that the sum of points possessed by the passengers who moved is within the range of -1,000,000,000 to 1,000,000,000.
__Parameters
_____mNum : The number of passengers to move by section ( 1 ≤ mNum ≤ 5, mNum * 2 ≤ M )
__Returns
_____ The sum of points possessed by the passengers who moved
[Example]
Let’s look into a case where functions are called as below.
#
Function
Description
Return
1
init(21,7,3,
{8,19,18,9,…...},
{2,0,2,1,…...})
There are 21 passengers. In a group of 7, they are in 3 sections.
There are 3 types of job in the train.
2
move(2)
After selecting the top 2 and bottom 2 by section,
the top 2 are brought to the section in front, while the bottom 2 are sent to the section behind.
75
3
move(2)
73
4
move(2)
68
5
update(2,796)
Passenger ID 2 earned 796 points.
814
6
updateByJob(0,-686)
Passengers of Job ID 0 all spent 686 points.
-5394
7
move(1)
-1330
8
update(17,-275)
-273
9
update(11,364)
-304
10
update(14,-76)
-76
11
move(2)
-2667
12
update(9,-172)
-171
13
update(1,-970)
-1637
14
update(11,207)
-97
15
move(1)
-1804
16
update(16,-690)
-1367
17
updateByJob(2,471)
3029
18
updateByJob(1,-649)
-5498
19
move(2)
-2677
20
move(2)
-4310
21
move(2)
-4707
22
update(2,-890)
395
23
move(1)
-2082
24
update(20,139)
-546
25
updateByJob(2,59)
2434
26
update(9,-589)
-230
The table below shows the status after executing each function.
The table with 2 rows shows the status before and after a movement.
The points possessed by passengers colored in red mean that they are negative numbers.
[Constraints]
1. For each test case, init() is called in the beginning and destroy() is called at the end.
2. For each test case, update() is called up to 10,000 times.
3. For each test case, updateByJob() is called up to 300 times.
4. For each test case, move() is called up to 1,000 times.
5. For each test case, the maximum number of people by job does NOT exceed 200.
[Input and Output]
As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.
The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.
#define MAX_N 100000
#define MAX_J 1000
#define opt __attribute((optimize("Ofast")))
int sectionNums;
struct Passengers {
public:
unsigned int id;
int point;
unsigned int Section;
unsigned int minId, maxId;
opt bool operator<(Passengers& mP) const {
if (this->point != mP.point)
return this->point < mP.point;
else
return this->id > mP.id;
}
} passengers[MAX_N];
struct Heap {
public:
int idList[14286];
bool isMaxHeap;
unsigned int size;
opt void initMaxHeap() {
this->isMaxHeap = true;
this->size = 0;
}
opt void initMinHeap() {
this->isMaxHeap = false;
this->size = 0;
}
opt void insert(int index) {
this->idList[this->size] = index;
if (isMaxHeap)
passengers[index].maxId = size;
else
passengers[index].minId = size;
heapifyUp(this->size++);
}
opt void heapifyUp(int index) {
int indx = index;
int parent = (indx - 1) / 2 ;
if (parent>= 0) {
if (comp(parent, indx) == isMaxHeap)
indx = parent;
}
if (indx != index) {
Swap(indx, index);
heapifyUp(indx);
}
}
opt void heapifyDown(int index) {
int indx = index,
left = 2 * indx + 1,
right = 2 * indx + 2;
if (left < size) {
if (comp(indx, left) == isMaxHeap)
indx = left;
}
if (right < size) {
if (comp(indx, right) == isMaxHeap)
indx = right;
}
if (indx != index) {
Swap(indx, index);
heapifyDown(indx);
}
}
opt void erase(int index) {
Swap(index, --this->size);
heapifyDown(index);
heapifyUp(index);
}
opt void update(int index) {
heapifyUp(index);
heapifyDown(index);
}
opt int pop() {
Swap(0, --this->size);
heapifyDown(0);
return this->idList[this->size];
}
opt void Swap(int a, int b) {
int t = idList[a];
idList[a] = idList[b];
idList[b] = t;
if (isMaxHeap) {
passengers[idList[a]].maxId = a;
passengers[idList[b]].maxId = b;
} else {
passengers[idList[a]].minId = a;
passengers[idList[b]].minId = b;
}
}
opt bool comp(int id1, int id2) {
return passengers[idList[id1]] < passengers[idList[id2]];
}
} Max[10], Min[10];
struct JobList {
public:
int idList[200];
int size;
opt void reset() {
size = 0;
}
opt void push(int id) {
idList[size++] = id;
}
opt int update(int point) {
int sum = 0;
for (register int i = 0; i < size; i++) {
passengers[idList[i]].point += point;
Min[passengers[idList[i]].Section].update(passengers[idList[i]].minId);
Max[passengers[idList[i]].Section].update(passengers[idList[i]].maxId);
sum += passengers[idList[i]].point;
}
return sum;
}
} jobList[MAX_J];
opt void init(int N, int M, int J, int mPoint[], int mJobID[]) {
sectionNums = N / M;
for (register int i = 0; i < sectionNums; i++) {
Min[i].initMinHeap();
Max[i].initMaxHeap();
}
for (register int i = 0; i < J; i++)
jobList[i].reset();
for (register int i = 0; i < N; i++) {
passengers[i].id = i;
passengers[i].point = mPoint[i];
passengers[i].Section = i / M;
jobList[mJobID[i]].push(i);
Max[i / M].insert(i);
Min[i / M].insert(i);
}
}
void destroy() {
}
opt int update(int mID, int mPoint) { // 10.000
passengers[mID].point += mPoint;
Max[passengers[mID].Section].update(passengers[mID].maxId);
Min[passengers[mID].Section].update(passengers[mID].minId);
return passengers[mID].point;
}
opt int updateByJob(int mJobID, int mPoint) { // 300
return jobList[mJobID].update(mPoint);
}
int t, toFront[10][5], toBack[10][5];
opt int move(int mNum) { // 1.000
int sum = 0;
for (register int s = 0; s < sectionNums - 1; s++) {
for (register int i = 0; i < mNum; i++) {
t = Min[s].pop();
Max[s].erase(passengers[t].maxId);
sum += passengers[t].point;
++passengers[t].Section;
toBack[s][i] = t;
}
}
for (register int s = 1; s < sectionNums; s++) {
for (register int i = 0; i < mNum; i++) {
t = Max[s].pop();
Min[s].erase(passengers[t].minId);
sum += passengers[t].point;
--passengers[t].Section;
toFront[s][i] = t;
}
}
for (register int s = 0; s < sectionNums; s++) {
for (register int i = 0; i < mNum; i++) {
if (s > 0) {
Min[s - 1].insert(toFront[s][i]);
Max[s - 1].insert(toFront[s][i]);
}
if (s < sectionNums - 1) {
Min[s + 1].insert(toBack[s][i]);
Max[s + 1].insert(toBack[s][i]);
}
}
}
return sum;
}