단, 각 격투기 선수들의 초기 전투력은 비내림차순으로 정렬되어 있다.
이 조건을 보면 뭔가 이분 탐색이 가능할 것 처럼 보인다. 번째 격투기 선수가 챔피언이 될 수 있다면, 그보다 전투력이 더 높은 번째 선수도 챔피언이 될 수 있다. 그런데 전투력이 서로 같은 선수들도 주어지기 때문에 번째 선수가 번째 선수보다 무조건 전투력이 더 높다고 할 수가 없다.
라고 하면
비내림차순이기 때문에 이 성립한다.
위에서 전투력이 서로 같은 선수들이 문제였는데, 같은 선수들 중에서는 맨 왼쪽을 제외하고는 모두 이므로 챔피언이 될 수 없다.
결국 우리가 확인해봐야할 것은 같은 선수들 중에 맨 왼쪽 선수들만 보면 되고, 이들만 확인한다면 위에서 증명했었던 단조 증가가 성립하기 때문에 이분 탐색이 가능해진다.
public class Main {
static int N; static int[] S;
// i번째 있는 사람이 챔피언이 될 수 있는지 반환
// 단 i번째는 같은 전투력을 가진 사람들 중에서 가장 왼쪽에 있음
static boolean f(int i) {
int here = i; int size = S[i];
while (here - 1 >= 0 && size > S[here - 1]) { size++; here--; }
if (here != 0) return false;
here = i;
while (here + 1 < N && size > S[here + 1]) { size++; here++; }
if (here != N - 1) return false;
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bw = new StringBuilder();
N = Integer.parseInt(br.readLine());
S = new int[N];
ArrayList<Integer> P = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
S[i] = Integer.parseInt(st.nextToken());
if (i == 0 || S[i] > S[i - 1]) P.add(i);
}
// lo번째 선수는 챔피언이 될 수 없고
// hi번째 선수는 챔피언이 될 수 있다고 가정
int lo = 0; int hi = P.size() - 1;
if (f(P.get(lo))) {
for (int x : P) bw.append(x + 1).append(" ");
System.out.println(bw.toString().trim());
} else if (!f(P.get(hi))) {
System.out.println(-1);
} else {
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (f(P.get(mid))) hi = mid;
else lo = mid;
}
for (int x : P) if (x >= P.get(hi))
bw.append(x + 1).append(" ");
System.out.println(bw.toString().trim());
}
}
}
이분 탐색을 통해 의 비교를 하고, 비교 한번에 이므로
10
1 2 3 4 5 6 7 8 9 10
->3 4 5 6 7 8 9 10
1
1
->1