Untitled

You are required to implement a delivery system where its users place orders for food and then the system recommends restaurants based on their order information.


Given user information – the number of users, their IDs, and the locations of where they live.
The location information is given with (x, y) coordinates whose range is from -1,000,000 to 1,000,000.


Restaurants can be added or deleted and their IDs and locations are also provided.


A particular customer can request a delivery from a particular restaurant and such request is registered in the system.


This delivery system allows users to befriend each other, using such information for restaurant recommendations.


When the user wants recommendations, the system selects and recommends 10 restaurants in the order of priority.


Priorities are determined following the below criteria:


1) A restaurant is high in priority if it has a bigger sum of orders placed by the customer him/herself and their friends.
2) If there several restaurants that meet 1), a restaurant that is the closest to the customer’s house is high in priority.
  ※ When the coordinates of the customer’s house are (px, py) and those of the restaurant are (rx, ry), the distance can be calculated by |px-rx| + |py-ry|.
3) If there several restaurants that meet 2), a restaurant, which has a smaller ID, is high in priority.


 


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 px[], int py[])

This function is called in the beginning of each test case.

The number of customers is N and the ID of each customer is given a number from 0, 1, to N-1.

The location of the customer’s house is given with coordinates from (px[0], py[0]), (px[1], py[1]), … to (px[N-1], py[N-1]).

It is guaranteed that the locations of customers’ houses are different.

 

Parameters

   N : Number of customers (2 ≤ N ≤ 25)

   px, py : Coordinates of each customer’s house (-1,000,000 ≤ px[i], py[i] ≤ 1,000,000)
   ※ i means the ID of the customer (0 ≤ i ≤ N-1)

void addRestaurant(int pID, int x, int y)

This function adds a restaurant on (x, y), whose ID is ‘pID.’

There is no restaurant or customer’s house on the same location.

 

It is guaranteed that a restaurant, whose ID is ‘pID,’ has never been added before.

 

Parameters

   pID : ID of the restaurant to be added (0 ≤ pID ≤ 999,999)

   x, y : Coordinates of the restaurant to be added (-1,000,000 ≤ x, y ≤ 1,000,000)

void removeRestaurant(int pID)

This function removes a restaurant whose ID is ‘pID.’

 

It is guaranteed that the restaurant, whose ID is ‘pID’, has been added and has never been removed before.

 

Parameters

   pID : ID of the restaurant to be removed (0 ≤ pID ≤ 999,999)

void order(int uID, int pID)

A customer, whose ID is ‘uID,’ orders food once at the restaurant whose ID is ‘pID.’

 

It is guaranteed that the restaurant, whose ID is ‘pID’, has been added and has never been removed before.

 

Parameters

   uID : ID of the customer who places the order (0 ≤ uID ≤ N-1)

   pID : ID of the restaurant which takes the order (0 ≤ pID ≤ 999,999)

void beFriend(int uID1, int uID2)

A customer, whose ID is ‘uID1’, befriends a customer whose ID is ‘uID2.’

 

It is guaranteed that uID1 and uID2 are different values.

There is no case where ‘uID1’ has already befriended ‘uID2.’

 

Parameters

   uID1, uID2 : ID of the customers who become friends with each other (0 ≤ uID1, uID2 ≤ N-1)

int recommend(int uID)

This function returns the ID of a restaurant which is 10th in priority among the ones recommended to ‘uID.’.

It is guaranteed that the number of restaurants is 10 or higher when this function is executed.

How to set priorities are explained above.

 

Parameters

   uID : ID of the customer who gets recommendations (0 ≤ uID ≤ N-1)

return

   ID of the 10th highest restaurant in priority


 


 


[Example]


Let’s look into a case where functions are called as below.


Order

Function

Recommend Top10

Return

Figure

1

init(5, px[]={1,3,2,4,5}, py[]={1,1,3,2,4})

 

 

 

2

addRestaurant(pID=0, x=2, y=2)

 

 

 

3

addRestaurant(pID=1, x=8, y=5)

 

 

 

4

addRestaurant(pID=2, x=8, y=7)

 

 

 

5

addRestaurant(pID=3, x=10, y=3)

 

 

 

6

addRestaurant(pID=4, x=1, y=6)

 

 

 

7

addRestaurant(pID=5, x=0, y=0)

 

 

 

8

addRestaurant(pID=6, x=-2, y=3)

 

 

 

9

addRestaurant(pID=7, x=1, y=-1)

 

 

 

10

addRestaurant(pID=8, x=4, y=0)

 

 

 

11

addRestaurant(pID=9, x=4, y=4)

 

 

[Fig.1]

12

order(uID=3, pID=4)

 

 

 

13

order(uID=1, pID=8)

 

 

 

14

order(uID=1, pID=8)

 

 

 

15

recommend(uID=3)

{4, 0, 8, 9, 5, 7, 1, 3, 6, 2}

2

[Table 1]

16

beFriend(uID1=1, uID2=3)

 

 

 

17

recommend(uID=3)

{8, 4, 0, 9, 5, 7, 1, 3, 6, 2}

2

[Table 2]

18

addRestaurant(pID=10, x=5, y=1)

 

 

 

19

removeRestaurant(pID=8)

 

 

[Fig.2]

20

order(uID=3, pID=10)

 

 

 

21

order(uID=1, pID=10)

 

 

 

22

recommend(uID=1)

{10, 4, 0, 5, 7, 9, 6, 1, 3, 2}

2

[Table 3]


 


[Fig. 1] shows the locations of each customer’s house and each restaurant after functions are executed until Order #11. Black dots represent restaurants while red house customers’ houses.



                                       [Fig.1]


 


At Order #15, the system recommends restaurants as below for a customer whose ID is 3.


Priority #

# of Orders

Distance

ID

1

1

7

4

2

0

2

0

3

0

2

8

4

0

2

9

5

0

6

5

6

0

6

7

7

0

7

1

8

0

7

3

9

0

7

6

10

0

9

2


                   [Table 1]


 


When a customer whose ID is 1 befriends a customer whose ID is 3 at Order #16, the number of orders placed by the customer 1 also affects restaurant recommendations for the customer 3.


Two customers befriend each other at Order #17, the system recommends restaurants for the customer 3.


Priority #

# of Orders

Distance

ID

1

2

2

8

2

1

7

4

3

0

2

0

4

0

2

9

5

0

6

5

6

0

6

7

7

0

7

1

8

0

7

3

9

0

7

6

10

0

9

2


                   [Table 2]


 


[Fig. 2] shows the locations of each customer’s house and each restaurant after functions are executed until Order #19.



                               [Fig.2]


 


At Order #22, the system recommends restaurants for the customer 1.


Priority #

# of Orders

Distance

ID

1

2

2

10

2

1

7

4

3

0

2

0

4

0

4

5

5

0

4

7

6

0

4

9

7

0

7

6

8

0

9

1

9

0

9

3

10

0

11

2


                   [Table 3]


 


 [Constraints]


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


2. For each test case, addRestaurant() can be called less or equal to 6,000 times.


3. For each test case, removeRestaurant() can be called less or equal to 1,000 times.


4. For each test case, order() can be called less or equal to 3,000 times.


5. For each test case, beFriend() can be called less or equal to 200 times.


6. For each test case, recommend() can be called less or equal to 10,000 times.


7. For each test case, there is no case where any restaurant or house is located in the same spot.



#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

extern void init(int N, int px[], int py[]);
extern void addRestaurant(int pID, int x, int y);
extern void removeRestaurant(int pID);
extern void order(int uID, int pID);
extern void beFriend(int uID1, int uID2);
extern int recommend(int uID);

#define INIT 100
#define ADD_RESTAURANT 200
#define REMOVE_RESTAURANT 300
#define ORDER 400
#define BE_FRIEND 500
#define RECOMMEND 600

static int px[30];
static int py[30];

static bool run()
{
	int query_num;
	scanf("%d", &query_num);

	int n = 0;
	bool ok = false;

	for (int q = 0; q < query_num; q++)
	{
		int query;
		scanf("%d", &query);

		if (query == INIT)
		{
			scanf("%d", &n);
			for (int i = 0; i < n; i++)
				scanf("%d", &px[i]);
			for (int i = 0; i < n; i++)
				scanf("%d", &py[i]);

			init(n, px, py);

			ok = true;
		}
		else if (query == ADD_RESTAURANT)
		{
			int pID, x, y;
			scanf("%d%d%d", &pID, &x, &y);

			addRestaurant(pID, x, y);
		}
		else if (query == REMOVE_RESTAURANT)
		{
			int pID;
			scanf("%d", &pID);

			removeRestaurant(pID);
		}
		else if (query == ORDER)
		{
			int uID, pID;
			scanf("%d%d", &uID, &pID);

			order(uID, pID);
		}
		else if (query == BE_FRIEND)
		{
			int uID1, uID2;
			scanf("%d%d", &uID1, &uID2);

			beFriend(uID1, uID2);
		}
		else if (query == RECOMMEND)
		{
			int uID, ans;
			scanf("%d %d", &uID, &ans);
			int ret = recommend(uID);
			if (ret != ans)
			{
				ok = false;
			}
		}
	}

	return ok;
}

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;
}



void init(int N, int px[], int py[])
{

}

void addRestaurant(int pID, int x, int y)
{

}

void removeRestaurant(int pID)
{

}

void order(int uID, int pID)
{

}

void beFriend(int uID1, int uID2)
{

}

int recommend(int uID)
{
	return 0;
}


25 100
22
100 5
1 3 2 4 5
1 1 3 2 4
200 0 2 2
200 1 8 5
200 2 8 7
200 3 10 3
200 4 1 6
200 5 0 0
200 6 -2 3
200 7 1 -1
200 8 4 0
200 9 4 4
400 3 4
400 1 8
400 1 8
600 3 2
500 1 3
600 3 2
200 10 5 1
300 8
400 3 10
400 1 10
600 1 2