Skip to content

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;
}