Untitled

[Problem Description]

There is a memory system. The whole size of memory is N and it has a consecutive unit of storage labeled with an address from 0 to N-1.
The requested size of memory storage when allocating memory is given as the number of units of storage.

A single empty space is when consecutive units of storage that were not allocated are grouped together.
At first, nothing is allocated so there is one empty space whose size is N. [Fig. 1] shows the initial state of memory whose size is 30.



[Fig. 1]

When allocating a memory space, it has to be consecutive and cannot be allocated by breaking it up into at least two blocks.
Thus, in order to allocate the requested memory to a certain empty space,
the size of the empty space must always be greater than or equal to the requested size. Best Fit Allocation is used for allocation.
In other words, allocate memory to the smallest-sized empty space among the empty spaces that can be used for storage.
If there are several smallest-sized empty spaces, allocate the memory to the one that comes first than any other empty spaces.

When releasing a memory space, the value of starting address, which is the value of address at the very front of a memory space, is given.
Then, change the memory space into an empty space. If there are empty spaces near it, merge them together.

Implement allocation and release of memory that operates as mentioned 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, the whole size of memory, is given. They are all empty spaces.

 

Parameters

  N : The size of memory ( 30 ≤ N ≤ 100,000,000 )

int allocate(int mSize)

This function requests the memory allocation whose size is mSize.

Among empty spaces that can store memory, allocate memory to the smallest-sized empty space. Thus, use Best Fit Allocation. If there are several empty spaces whose size are the smallest, allocate memory to the empty space that comes first than any other empty spaces.

If allocation is successful, return the value of starting address of the allocated memory space.

If there is NO empty space that can be allocated, return -1.

 

Parameters

  mSize: The size of memory for which allocation is requested ( 1 ≤ mSize ≤ N )

 

Returns

  Return the value of starting address of the allocated memory space.

  If the allocation fails, return -1.

int release(int mAddr)

This function requests the release of the memory whose value of starting address is mAddr.

If the value of mAddr is not the value of starting address or if it is already an empty space, the release fails. Thus, return -1.

If that is not the case, change the memory space into an empty space and when there are empty spaces near it, merge them together.
In addition, return the size of the released memory space.

 

Parameters

  mAddr: The memory address for which release is requested ( 0 ≤ mAddr ≤ N - 1 )

 

Returns

  Return the size of the released memory space.

  If the release fails, return -1.

 

[Example]

Let’s look into a case where functions are called as [Table 1] below.

Order

Function

return

Figure

1

init(30)

 

Fig. 1

2

allocate(13)

0

Fig. 2

3

release(5)

-1

 

4

allocate(7)

13

Fig. 3

5

allocate(3)

20

Fig. 4

6

allocate(10)

-1

 

7

release(13)

7

Fig. 5

8

allocate(3)

13

Fig. 6

9

release(0)

13

Fig. 7

10

allocate(3)

16

Fig. 8

11

release(20)

3

Fig. 9

12

allocate(8)

19

Fig. 10

13

release(0)

-1

 

[Table 1]

(Order 1) Memory sized 30 is created. At first, everything is an empty space.

(Order 2) Memory allocation sized 13 is requested. Currently, there is only one empty space whose size is 30.
Thus, allocate the memory to the range from No. 0 to 12 and return 0 as the value of starting address.
[Fig. 2] shows the result of function call.



[Fig. 2]

(Order 3) Memory release is requested for the address value of 5.
However, as the address value is NOT the starting address of the allocated memory, the release fails. Thus, return -1.

(Order 4) Memory allocation sized 7 is requested. Currently, there is only one empty space whose size is 17.
Thus, allocate the memory to the range from No. 13 to 19 and return 13 as the value of starting address.
[Fig. 3] shows the result of function call.



[Fig. 3]

(Order 5) Memory allocation sized 3 is requested. Currently, there is only one empty space whose size is 10.
Thus, allocate the memory to the range from No. 20 to 22 and return 20 as the value of starting address.
[Fig. 4] shows the result of function call.



[Fig. 4]

(Order 6) Memory allocation sized 10 is requested.
Currently, as there is NO empty space for the allocation, the allocation fails. Thus, return -1.

(Order 7) Memory release is requested for the address value of 13. Change the memory space into an empty space.
Then, return 7, the size of the released memory space. [Fig. 5] shows the result of function call.



[Fig. 5]

(Order 8) Memory allocation sized 3 is requested.
Currently, the smallest size of empty space for storage is 7 and there are two of it.
Among the two, allocate the memory to the empty space that comes first than the other.
Thus, allocate the memory to the range from No. 13 to 15 and return 13 as the value of starting address.
[Fig. 6] shows the result of function call.



[Fig. 6]

(Order 9) Memory release is requested for the address value of 0.
Change the memory space into an empty space. Then, return 13, the size of the released memory space.
[Fig. 7] shows the result of function call.



[Fig. 7]

(Order 10) Memory allocation sized 3 is requested. Currently, the smallest size of empty space for storage is 4.
Allocate the memory to the range from No. 16 to 18 and return 16 as the value of starting address.
[Fig. 8] shows the result of function call.



[Fig. 8]

(Order 11) Memory release is requested for the address value of 20.
Change the memory space into an empty space and merge it with the empty spaces nearby.
Then, return 3, the size of the released memory space. [Fig. 9] shows the result of function call.



[Fig. 9]

(Order 12) Memory allocation sized 8 is requested. The smallest size of empty space for storage is 11.
Allocate the memory to the range from No. 19 to 26 and return 19 as the value of starting address.
[Fig. 10] shows the result of function call.



[Fig. 10]

(Order 13) Memory release is requested for the address value of 0.
However, as the address value is NOT the starting address of the allocated memory, the release fails. Thus, return -1.

 

[Constraints]

1. init() is called in the beginning of each test case.

2. For each test case, the sum of calls of the all functions is less than or equal to 30,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.