Untitled
unknown
plain_text
a year ago
12 kB
9
Indexable
There is a system that allocates N lockers.
Lockers are in a row at equal intervals and numbered from 1 to N in order.
When a user arrives at the room, allocate a locker to the user under the following rules.
- If all the lockers are empty, allocate Locker 1.
- If not, first select the longest section of consecutive empty lockers.
If there are two or more of such sections, select the section containing the smallest locker number.
Within the selected section, allocate a locker which is the farthest from a locker being used.
If there are two or more of such lockers, allocate the locker with the smallest number.
When a user leaves the room, the locker allocated to the user becomes empty.
You are required to implement a system that allocates lockers operating as above.
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)
This function is called in the beginning of each test case.
N lockers are given and all of them are empty.
Parameters
N: The number of lockers ( 8 ≤ N ≤ 100,000,000 )
int arrive(int mId)
This function makes User mId arrive at the room.
There is no case when mId is given as an ID of a user who is using a locker.
There is no case when this function is called in a state of no empty lockers.
This function allocates a locker under the rules of allocation.
This function returns the locker number allocated.
Parameters
mId: User ID ( 1 ≤ mId ≤ 1,000,000,000 )
Returns
Return the locker number allocated.
int leave(int mId)
This function makes User mId leave the room.
mId is given only as an ID of a user who is using a locker.
This function empties the locker that was allocated to User mId. Thus, the locker becomes empty.
This function returns the number of empty lockers after emptying.
Parameters
mId: The User ID ( 1 ≤ mId ≤ 1,000,000,000 )
Returns
Return the number of empty lockers.
[Example]
Let’s look into a case when functions are called as in [Table 1] below.
Order
Function
return
Figure
1
init(8)
2
arrive(200)
1
3
arrive(100)
8
Fig. 1
4
arrive(700)
4
Fig. 2
5
arrive(600)
6
Fig. 3
6
leave(200)
5
Fig. 4
7
arrive(300)
1
Fig. 5
8
arrive(800)
2
Fig. 6
9
arrive(200)
3
Fig. 7
10
leave(600)
3
11
leave(100)
4
Fig. 8
12
arrive(400)
8
Fig. 9
[Table 1]
(Order 1) 8 lockers are given. In the beginning, they are all empty.
(Order 2) User 200 arrives at the room. As all the lockers are empty, allocate Locker 1.
(Order 3) User 100 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 2 to Locker 8.
As the locker farthest from the locker being used is Locker 8, return 8. [Fig. 1] shows the result of function call.
[Fig. 1]
(Order 4) User 700 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 2 to Locker 7.
Lockers farthest from the lockers being used are Locker 4 and Locker 5. Between the two, allocate Locker 4 whose number is smaller and return 4.
[Fig. 2] shows the result of function call.
[Fig. 2]
(Order 5) User 600 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 5 to Locker 7.
As the locker farthest from the lockers being used is Locker 6, return 6. [Fig. 3] shows the result of function call.
[Fig. 3]
(Order 6) User 200 leaves the room. Locker 1 becomes empty. For the total number of empty lockers, return 5.
[Fig. 4] shows the result of function call.
[Fig. 4]
(Order 7) User 300 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 1 to Locker 3.
As the locker farthest from the lockers being used is Locker 1, return 1. [Fig. 5] shows the result of function call.
[Fig. 5]
(Order 8) User 800 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 2 to Locker 3.
Lockers farthest from the lockers being used are Locker 2 and Locker 3. Between the two, allocate Locker 2 whose number is smaller and return 2.
[Fig. 6] shows the result of function call.
[Fig. 6]
(Order 9) User 200 arrives at the room.
The longest sections of consecutive empty lockers are ranging from Locker 3 to Locker 3, from Locker 5 to Locker 5, and from Locker 7 to Locker 7.
Among them, choose the section from Locker 3 to Locker 3, as it contains the locker with the smallest number.
As the locker farthest from the lockers being used is Locker 3, return 3. [Fig. 7] shows the result of function call.
[Fig. 7]
(Order 10) User 600 leaves the room. Locker 6 becomes empty. For the total number of empty lockers, return 3.
(Order 11) User 100 leaves the room. Locker 8 becomes empty. For the total number of empty lockers, return 4.
[Fig. 8] shows the result of function call.
[Fig. 8]
(Order 12) User 400 arrives at the room. The longest section of consecutive empty lockers is ranging from Locker 5 to Locker 8.
As the locker farthest from the lockers being used is Locker 8, return 8. [Fig. 9] shows the result of function call.
[Fig. 9]
[Constraints]
1. init() is called in the beginning of each test case.
2. For each test case, arrive() is called up to 20,000 times.
3. For each test case, the sum of calls of the all functions is less than or equal to 35,000.
[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.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N);
extern int arrive(int mId);
extern int leave(int mId);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_ARRIVE 2
#define CMD_LEAVE 3
static bool run() {
int q;
scanf("%d", &q);
int n, mid;
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);
init(n);
okay = true;
break;
case CMD_ARRIVE:
scanf("%d %d", &mid, &ans);
ret = arrive(mid);
if (ans != ret)
okay = false;
break;
case CMD_LEAVE:
scanf("%d %d", &mid, &ans);
ret = leave(mid);
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;
}
#define MAX_SECTION 40005
#define NULL 0
#define MAXADD 20011
int N;
int emptyLockers;
struct Section {
int start;
int end;
int heapIdx;
int uId;//If not locked, uId = 0
Section* next;
Section* prev;
Section* nextInMap;
} sections[MAX_SECTION];
int sectionNum;
Section* newSection(int st, int en)
{
Section* section = §ions[sectionNum++];
section->start = st;
section->end = en;
section->uId = 0;
return section;
}
//HashMap
Section* HashTable[MAXADD];
void addToHashMap(Section* section)
{
int idx = section->uId % MAXADD;
section->nextInMap = HashTable[idx];
HashTable[idx] = section;
}
Section* findSection(int id)
{
int idx = id % MAXADD;
for (Section* section = HashTable[idx]; section; section = section->nextInMap)
if (id == section->uId)
return section;
return NULL;
}
//Doubly linked list
Section* listHead = new Section();
Section* listTail = new Section();
void link(Section* s1, Section* s2)
{
s1->next = s2;
s2->prev = s1;
}
void addFront(Section* s, Section* target)
{
link(target->prev, s);
link(s, target);
}
void removeFromList(Section* s)
{
link(s->prev, s->next);
}
//Heap
Section* mHeap[MAXADD];
int hSize;
bool better(Section* s1, Section* s2)
{
return (s1->end - s1->start > s2->end - s2->start) || (s1->end - s1->start == s2->end - s2->start && s1->start < s2->start);
}
void heapSwap(int i, int j)
{
Section* tmp = mHeap[i];
mHeap[i] = mHeap[j];
mHeap[j] = tmp;
mHeap[i]->heapIdx = i;
mHeap[j]->heapIdx = j;
}
int upHeapify(int idx)
{
while (idx > 1 && better(mHeap[idx], mHeap[idx >> 1])) {
heapSwap(idx, idx >> 1);
idx >>= 1;
}
return idx;
}
void downHeapify(int idx)
{
int child;
while ((child = idx << 1) <= hSize) {
if (child < hSize && better(mHeap[child + 1], mHeap[child]))
child++;
if (better(mHeap[child], mHeap[idx])) {
heapSwap(idx, child);
idx = child;
} else
return;
}
}
void heapPush(Section* section)
{
mHeap[++hSize] = section;
section->heapIdx = hSize;
upHeapify(hSize);
}
void heapDel(int pos)
{
heapSwap(pos, hSize--);
upHeapify(pos);
downHeapify(pos);
}
//End of data structures implementation.
void lock(Section* section, int pos, int uId)
{
Section * lockedSection = newSection(pos, pos);
lockedSection->uId = uId;
addToHashMap(lockedSection);
if (pos == section->end) {//when locked position is N
section->end = pos - 1;
downHeapify(section->heapIdx);
addFront(lockedSection, section->next);
return;
}
int oldStart = section->start;
section->start = pos + 1;
downHeapify(section->heapIdx);
addFront(lockedSection, section);
if (oldStart < pos) {
Section* prevSection = newSection(oldStart, pos - 1);
addFront(prevSection, lockedSection);
heapPush(prevSection);
}
}
void unlock(Section* section)
{
if (section->prev->uId && section->next->uId) { //both previous and next are locked
section->uId = 0;
heapPush(section);
return;
}
bool hasPrev = false;
if (!section->prev->uId) { //if previous is not locked, merge this section into previous
hasPrev = true;
removeFromList(section);
section->prev->end = section->end;
upHeapify(section->prev->heapIdx);
section = section->prev;
}
if (!section->next->uId) {//if next is not locked, merge to next
if (hasPrev) {
heapDel(section->heapIdx);
}
removeFromList(section);
section->next->start = section->start;
upHeapify(section->next->heapIdx);
}
}
void init(int N)
{
sectionNum = 0;
::N = emptyLockers = N;
for (register int i = 0; i < MAXADD; i++)
HashTable[i] = NULL;
listHead->uId = listTail->uId = 1000000000;
hSize = 0;
link(listHead, listTail);
Section* s = newSection(1, N);
addFront(s, listTail);
heapPush(s);
}
int arrive(int mId)
{
emptyLockers--;
Section* section = mHeap[1];
if (section->start == section->end) {
heapDel(1);
section->uId = mId;
addToHashMap(section);
return section->start;
}
int lockPos;
if (section->start == 1)
lockPos = 1;
else if (section->end == N)
lockPos = N;
else
lockPos = (section->start + section->end) >> 1;
lock(section, lockPos, mId);
return lockPos;
}
int leave(int mId)
{
Section* section = findSection(mId);
unlock(section);
return ++emptyLockers;
}