4029번: Condorcet Winners

https://www.acmicpc.net/problem/4029


$O(tbc)$

f(x,y): x, y 사이 콩도르세 승자
승자만 남는 식으로 두 후보자를 비교하면 c-1번의 f를 사용해서 최종 우승 후보자 p를 찾을 수 있다.
p를 다른 후보와 한 번씩 f를 통해 비교하면 콩도르세 우승자를 결정할 수 있다.

#include<cstdio>
int t, idx[500][2500], b, c;
int f(int x, int y) {
    int w = 0;
    for (int i = 0; i < b; i++) w += 1 - 2 * (idx[i][x] < idx[i][y]);
    return w<0 ? x : y;
}
int main() {
    for (int t = 1; scanf("%d %d", &b, &c) && b; t++) {
        int i, j, x, p = 0;
        for (i = 0; i < b; i++)for (j = 0; j < c; j++) scanf("%d", &x), idx[i][x] = j;
        for (i = 1; i < c; i++) p = f(p, i);
        for (i = 0; i < c; i++) if (i^p&&f(p, i) ^ p) break;
        printf("Case %d: ", t);
        i^c ? puts("No Condorcet winner") : printf("%d\n", p);
    }
    return 0;
}