유신장군과 돌장군 (Two Generals)

문제

인덱스국 전쟁사 : Day 3

펜윅국의 맹렬한 공격 아래 인덱스국의 도시는 하나둘 폐허가 되어갔고, 중군을 이끌던 명장 앤디 또한 펜윅국에 사로잡히고 말았습니다. (검열됨)에게 남은 마지막 희망은 수도를 지키는 유신장군과 돌장군입니다.

결전에 앞서 (검열됨)은 인덱스국 대대로 내려오는 N개의 무기들을 두 장수에게 하사하여 무장을 시키려고 합니다. 무기의 위력은 1, ···, M 범위의 정수로 표현되며, 무기를 여러 개 장착했을 때의 총 위력은 장착한 무기들의 위력을 합산한 값입니다.

안타깝게도, 펜윅국과 다르게 인덱스국은 아직도 뭔가를 '절반'으로 나누는 고루한 관습을 버리지 못했습니다. 따라서 (검열됨)은 두 장수가 장착한 무기의 위력이 정확히 같도록 무기를 분배하려고 합니다. 두 장수가 마지막 결전을 치룰 수 있게 도와주도록 합시다.

구현 세부 사항

다음 함수를 구현하세요.

int[] divideWeapons(int M, int P[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• M은 무기의 위력 범위입니다.
• P는 크기 N의 배열로, 모든 0 ≤ i ≤ N − 1에 대해 i + 1번 무기의 위력은 P[i]입니다.
• 이 함수는 유신장군이 가져가는 무기들의 번호를 나타내는 배열을 반환해야 합니다. 이 값들은 1, ···, N 범위에 있어야 하며, 중복되지 않아야 합니다.

제한 조건

• 1 ≤ M ≤ N ≤ 1,000,000
• 1 ≤ P[i] ≤ M
• 임의의 1 ≤ i ≤ M 에 대해 P[j] = i를 만족하는 j가 존재합니다.
• $\sum_{i=0}^{N-1} \text{P[i]}$는 짝수입니다.

서브태스크

• 이 문제는 부분 점수 문제입니다. 모든 무기의 위력의 합을 $S$, 유신장군이 가져간 무기의 위력의 합을 $Z$라고 하면, 여러분이 얻게 되는 점수는 해당 테스트 데이터의 만점에 $0.8^{\left|\frac{S}{2} - Z\right|}$를 곱한 값을 소수점 넷째 자리에서 반올림한 값입니다.

서브태스크	점수	N
1	3	N ≤ 15
2	3	N ≤ 200
3	3	N ≤ 3,000
4	6	N ≤ 1,000,000

예제 입출력

M = 3, P = [1, 3, 2]

그레이더는 다음 함수를 호출합니다.

divideWeapons(3, [1, 3, 2]) = [3]

예제에서 $S = 6$, $Z = 2$이기 때문에, 해당 테스트 케이스의 만점의 $0.8^{|6/2 - 2|} = 0.8$을 곱한 점수를 받습니다.

샘플 그레이더

샘플 그레이더는 다음의 형식으로 입력을 받습니다.

• line 1 : N M
• line 2 : P[0] P[1] ··· P[N − 1]