- P157's solution
P157's Solution
- 2025-9-10 17:16:06 @
在合法的排名表中,不难发现以下性质:
- 如果 A 的成绩比 B 高,那么 B 的成绩比 A 低。
- 如果 C 的成绩比所有人都高,那么他(她)是第一名。
- 在上面一条的基础上,每出现一个比 C 成绩高的选手,C 的排名就增加一名。
根据以上性质确定所有人的排名后一一代入验证即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 12;
char c[N][N];
int rk[N];
int sta[N];
int main()
{
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
int T;
scanf("%d ", &T);
while (T--)
{
int n;
scanf("%d ", &n);
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i - 1; j++)
{
scanf("%c ", &c[i][j]);
c[j][i] = '>' + '<' - c[i][j];
}
for (int i = 1; i <= n; i++)
{
rk[i] = 1;
for (int j = 1; j <= n; j++)
if (i != j && c[i][j] == '<') rk[i]++;
}
bool ok = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i == j) continue;
if (rk[i] <= rk[j] && c[i][j] == '<') ok = false;
if (rk[i] >= rk[j] && c[i][j] == '>') ok = false;
}
if (!ok)
{
for (int i = 1; i <= n - 1; i++)
printf("-1 ");
puts("-1");
}
else
{
for (int i = 1; i <= n; i++)
sta[rk[i]] = i;
for (int i = 1; i <= n - 1; i++)
printf("%d ", sta[i]);
printf("%d\n", sta[n]);
}
}
return 0;
}