11324: 【原1324】basketball

题目描述

author: 白志豪原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1324

Description

运动会马上就要开始了。助教对篮球很感兴趣，所以组织了一系列的篮球赛，并且为大家准备了丰厚的奖金。

助教对参加比赛的2n支球队的战斗力做了评估，并且按评估值从小到大的顺序给他们编号为0, 1, 2, …, 2n-1。但是助教的评估是不准确。另外，有些队伍虽然战斗力较低，但是他们的战术可能克制某个战斗力高的队伍。所以，如果队伍i的实际战斗力数值整除队伍j的实际战斗力，那么队伍i就会胜出比赛，否则实际战斗力更高的队伍会胜出比赛。保证没有两支队伍的实际战斗力相等。

赢得比赛的人会获得1点的奖金。此外，如果比赛爆冷，即评估值较低的队伍获得了胜利，那么将额外获得1点的奖金。在每一轮比赛开始前，所有队伍的奖金都是0。助教会将所有的队伍进行排序。当前奖金较低的队伍排在前面；对于奖金数相等的队伍，评估值更低的队伍排在前面。第2i支队伍与第2i+1支队伍进行比赛（0 <= i < n）。一共进行R轮比赛。

助教请你帮忙计算这2n支队伍最后获得的奖金数目。

Input Format

第一行有两个正整数N,R；

第二行有2n个正整数，第i个数据表示队伍i的实际战斗力。

Output Format

一行2n个整数，中间用空格隔开，第i个数字表示队伍i获得的奖金

Sample Input

5 3
1 2 3 4 5 6 7 8 9 10

Sample Output

6 0 1 2 1 1 2 2 1 2

Constraints

对于40%的数据，1 <= 1000, R<= 10；

对于70%的数据，1 <= n <= 10000,R <= 100;

对于100%的数据，1 <= n <= 50000, R <= 500.

WashSwang's solution

#include <iostream>
using namespace std;
struct team{
    int p,m,t; //p:power  m:money  t:team number
};
team s[110000],tmp[110000],cold[110000],win[110000],lose[110000];
int a,b,r,n,coldn,winn,losen,ans[110000];
void merge(team *r, team *s, team *t, int l1, int l2){
    int i=0,j=0,index=0;
    while (i<l1&&j<l2){
        if (s[i].m<t[j].m) r[index++]=s[i++];
        else if (s[i].m>t[j].m) r[index++]=t[j++];
        else if (s[i].t<t[j].t) r[index++]=s[i++];
        else r[index++]=t[j++];
    }
    if (i<l1) while (i<l1) r[index++]=s[i++];
    if (j<l2) while (j<l2) r[index++]=t[j++];
}
int main() {
    scanf("%d%d",&n,&r);
    for (int i=0;i<2*n;++i){
        scanf("%d",&s[i].p);
        s[i].t=i;
    }
    for (int i=0;i<r;++i){
        coldn=winn=losen=0;
        for (int j=0;j<n;++j){
            a=j<<1;
            b=a|1;
            if (s[a].p%s[b].p==0||(s[b].p>s[a].p&&s[b].p%s[a].p!=0)){
                if (s[b].t>s[a].t){
                    s[b].m+=1;
                    win[winn++]=s[b];
                    lose[losen++]=s[a];
                }
                else{
                    s[b].m+=2;
                    cold[coldn++]=s[b];
                    lose[losen++]=s[a];
                }
            }
            else{
                if (s[b].t<s[a].t){
                    s[a].m+=1;
                    win[winn++]=s[a];
                    lose[losen++]=s[b];
                }
                else{
                    s[a].m+=2;
                    cold[coldn++]=s[a];
                    lose[losen++]=s[b];
                }
            }
        }
        merge(tmp,win,cold,winn,coldn);
        merge(s,tmp,lose,winn+coldn,losen);
    }
    for (int i=0;i<2*n;++i)
        ans[s[i].t]=s[i].m;
    for (int i=0;i<2*n;++i)
        printf("%d ",ans[i]);
    return 0;
}