POJ1030 Rating

造福后人，必须翻译一下这痛苦的描述了。

按照AC后的理解来说，题目给出两场比赛编号1~100的队伍名次情况（有些队伍没有出现），每行是并列名次，下一行是前面队伍个数累计的名次，求两场比赛的总排名。

对于两场都参加的队伍，两场名次之和较小的排前面。

对于只参加一场的队伍，在不冲突的情况下和与其该场同名次的且参加了两场的另一支队伍总排名相同。

对于不满足上述的只参加一场的队伍，看是否可以插入一个位置，这个位置前面的队伍都是该场在其前面的队伍，后面的队伍也都是该场在其后面的队伍。多个能插入同位置的队伍，按他们在自己那一场的排名来比较。

对于以上条件都不满足的队伍，忽略掉。

输出的时候同名次队伍要在一行中按队伍ID升序输出。

  1 //把只参加一场的另一场名次赋值为同一场同名次队伍另一场的名次，但是不直接赋值，而
  2 //先缓存（nex），并统计缓存次数（cgcnt），如果缓存仅一次，即没有总名次不同队伍的
  3 //冲突，则真正把另一场赋值为nex。之后进行第一次排序。
  4 //对于只参加一场而无其他参加两场的同名次队伍时，判断是否可合理插入，记录插入位置
  5 //之后进行第二次排序，针对这次处理的这类队伍进行比较。
  6 //输出，终名次相同者输出在同一行。
  7 //单独写了完整的名次比较函数Compab()，函数中顺带处理了前两点所需数据。
  8 #include<stdio.h>
  9 #include<string.h>
 10 #include<stdlib.h>
 11 #include<ctype.h>
 12 const int maxn = 101;
 13 typedef struct
 14 {
 15     int rt[2];
 16     int num;
 17     int nex;
 18     int cgcnt;
 19     int share;
 20 } TEAM;
 21 TEAM te[maxn];
 22 int n, m;
 23 char buf[10001];
 24 void ReadData(int n, int ith)
 25 {
 26     int i, j, rank, cnt, tnum;
 27     for(i = rank = 1; i <= n; ++ i, rank += cnt)
 28     {
 29         gets(buf);
 30         for(j = cnt = 0; buf[j]; ++ j)
 31         {
 32             if(isdigit(buf[j]))
 33             {
 34                 sscanf(buf + j, "%d", &tnum);
 35                 te[tnum].rt[ith] = rank, ++ cnt;
 36                 te[tnum].num = tnum;
 37                 while(isdigit(buf[j])) ++ j;
 38                 -- j;
 39             }
 40         }
 41     }
 42 }
 43 int Compab(TEAM &a, TEAM &b)
 44 {
 45     if((a.rt[0] || a.rt[1]) && !(b.rt[0] || b.rt[1])) return -1;
 46     if(!(a.rt[0] || a.rt[1]) && (b.rt[0] || b.rt[1])) return 1;
 47     if(a.cgcnt == -1 && b.cgcnt != -1) return a.rt[0] ? a.rt[0] - b.rt[0] : a.rt[1] - b.rt[1];
 48     if(b.cgcnt == -1 && a.cgcnt != -1) return b.rt[0] ? a.rt[0] - b.rt[0] : a.rt[1] - b.rt[1];
 49     if(a.cgcnt == -1 && b.cgcnt == -1)
 50     {
 51         if(a.share == b.share)
 52             return a.rt[0] ? a.rt[0] - (b.rt[0] ? b.rt[0] : b.rt[1]) : a.rt[1] - (b.rt[1] ? b.rt[1] : b.rt[0]);
 53         return a.share - b.share;
 54     }
 55     if(a.rt[0] && a.rt[1] && !(b.rt[0] && b.rt[1]))
 56     {
 57         if(b.rt[0] == a.rt[0])
 58         {
 59             if(!b.nex || b.nex + b.rt[0] == a.rt[0] + a.rt[1])
 60                 b.nex = a.rt[1], b.share = a.num;
 61             else ++ b.cgcnt;
 62         }
 63         else if(b.rt[1] == a.rt[1])
 64         {
 65             if(!b.nex || b.nex + b.rt[1] == a.rt[0] + a.rt[1])
 66                 b.nex = a.rt[0], b.share = a.num;
 67             else ++ b.cgcnt;
 68         }
 69         return -1;
 70     }
 71     if(b.rt[0] && b.rt[1] && !(a.rt[0] && a.rt[1]))
 72     {
 73         if(a.rt[0] == b.rt[0])
 74         {
 75             if(!a.nex || a.nex + a.rt[0] == b.rt[0] + b.rt[1])
 76                 a.nex = b.rt[1], a.share = b.num;
 77             else ++ a.cgcnt;
 78         }
 79         else if(a.rt[1] == b.rt[1])
 80         {
 81             if(!a.nex || a.nex + a.rt[1] == b.rt[0] + b.rt[1])
 82                 a.nex = b.rt[0], a.share = b.num;
 83             else ++ a.cgcnt;
 84         }
 85         return 1;
 86     }
 87     if((a.rt[0] && a.rt[1]) && (b.rt[0] && b.rt[1]))
 88         return a.rt[0] + a.rt[1] - b.rt[0] - b.rt[1];
 89     if((a.rt[0] || a.rt[1]) && (b.rt[0] || b.rt[1]))
 90     {
 91         if(a.rt[0] && b.rt[0]) return a.rt[0] - b.rt[0];
 92         if(a.rt[1] && b.rt[1]) return a.rt[1] - b.rt[1];
 93         return 0;
 94     }
 95 }
 96 int comp(const void *a, const void *b)
 97 {
 98     return Compab(*(TEAM *)a, *(TEAM *)b) ? Compab(*(TEAM *)a, *(TEAM *)b) : (*(TEAM *)a).num - (*(TEAM *)b).num;
 99 }
100 int Judge(TEAM &a, int ith)
101 {
102     int i, j;
103     for(i = 1; te[i].rt[0] && te[i].rt[1] && i < maxn; ++ i)
104         if(te[i].rt[ith] > a.rt[ith]) break;
105     j = i;
106     for(; te[i].rt[0] && te[i].rt[1] && i < maxn; ++ i)
107         if(te[i].rt[ith] <= a.rt[ith]) break;
108     if(j < maxn && (Compab(te[j - 1], te[j]) == 0 || te[i].rt[0] && te[i].rt[1]))
109         return a.rt[0] = a.rt[1] = a.cgcnt = 0;
110     return a.cgcnt = -1, j;
111 }
112 int main()
113 {
114     int i, j, k;
115     while(scanf("%d\n", &n) != EOF)
116     {
117         memset(te, 0, sizeof(te));
118         for(i = 0; i < maxn; ++ i) te[i].num = i;
119         ReadData(n, 0);
120         scanf("%d\n", &m);
121         ReadData(m, 1);
122         for(i = 1; i < maxn; ++ i)
123             for(j = i + 1; j < maxn; ++ j)
124                 Compab(te[i], te[j]);
125         for(i = 1; i < maxn; ++ i)
126         {
127             if(te[i].cgcnt) te[i].rt[0] = te[i].rt[1] = 0;
128             else if(te[i].nex)
129             {
130                 if(te[i].rt[0]) te[i].rt[1] = te[i].nex;
131                 else te[i].rt[0] = te[i].nex;
132             }
133         }
134         qsort(te + 1, 100, sizeof(TEAM), comp);
135         for(i = 1; i < maxn; ++ i)
136         {
137             if(te[i].rt[0] && !te[i].rt[1])
138                 te[i].share = Judge(te[i], 0);
139             else if(!te[i].rt[0] && te[i].rt[1])
140                 te[i].share = Judge(te[i], 1);
141         }
142         qsort(te + 1, 100, sizeof(TEAM), comp);
143         for(i = 1; (te[i].rt[0] || te[i].rt[1]) && i < maxn; i = j)
144         {
145             printf("%d", te[i].num);
146             for(j = i + 1; (te[j].rt[0] || te[j].rt[1]) && !Compab(te[i], te[j]); ++ j)
147                 printf(" %d", te[j].num);
148             printf("\n");
149         }
150     }
151     return 0;
152 }