루미 알고리즘

#1569플래티넘Santa Planning Building

PO 2023 온라인 예선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

According to the UN, the world's population reached 8 billion people in November 2022. One person who clearly notices this is Santa Claus. He has to deliver presents to several billion children.

Unfortunately, Santa will not have time to deliver presents to all the children this year. Instead, he needs to choose a group of children to receive presents. To make it fair, he plans to give presents to exactly half of all the children, while the other half will go without. This way, the two groups will contain exactly the same number of children, and no group will be envious of the other. “Perfectly balanced”, as Santa often says.

You are responsible for planning which houses Santa should visit. There are N houses numbered from 1 to N, where house number i has coordinates (x_i, y_i). Traveling between two points (x_i, y_i) and (x_j, y_j) takes |x_i - x_j| + |y_i - y_j| seconds (|a| is the mathematical notation for the absolute value of the number a, defined as a if a ≥ 0 and -a if a < 0.). Your task is to find an ordered list of N/2 different houses (N is always even), such that the total time to visit the houses in that order is as small as possible. Santa starts his journey at the first house in your list and finishes it at the last house in your list.

Input

The input consists of 10 test cases.

The first line contains an integer T (0 ≤ T ≤ 10), the number of the test case (0 is the sample case below).

The second line contains an integer N (1 ≤ N ≤ 10^5), the number of houses. N is guaranteed to be even.

The following N lines each contain two integers x_i and y_i (0 ≤ x_i, y_i ≤ 10^6), the coordinates of the i-th house. No two houses are located at the same coordinates.

Output

Print N/2 space-separated integers, the numbers of the houses to be visited in order.

Points

Your program will be tested on 10 test cases and scored based on how it compares to the judges' solution.

Let P_1 be the total distance Santa needs to travel in your solution, and let P_2 be the corresponding distance for the judges' solution. You will then receive min(10 · (P_2)/(P_1), 10) points for the test case. You can never receive more than 10 points for a test case, even if your solution is better than the judges' solution. However, the judge might show a higher score per test case in the submission details interface so that you can see exactly how good your solution is.

Your score for a submission is the sum of the scores for the test cases, and your total score is the score of your best submission. Thus, it is not possible to combine test cases from different submissions; instead, you must submit a single program that maximizes your score on all test cases simultaneously.

The example test case will always give 0 points.

Testcases

Here are descriptions of the 10 test cases that occur. In all test cases, the coordinates are guaranteed to have been generated uniformly at random between 0 and 10^6, unless otherwise specified.

GroupPoint valueConstraints
1N = 10^5y_i = 0 for all i
2N = 10^50 ≤ y_i ≤ 20 for all i
3N = 10
4N = 40
5N = 200
6N = 800
7N = 7000
8N = 40000
9N = 80000
10N = 10^5

Explanation of sample 1

In the example case, the example solution achieves a total distance of 40 because the distance between house 2 and house 4 is 5, and the distance between house 4 and house 1 is 35. There are several ways to achieve a better answer, for example by visiting the houses in the order 4 2 1. Then the total distance becomes 35 instead.

예제

예제 1

입력
0
6
0 0
10 20
1000000 1000000
15 20
10 30
50 60
출력
2 4 1

출처 표기

출처: Programmeringsolympiaden 2023년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.