absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[搬家]Codeforces 576B
POJ 3910 解题报告

100506 I 解题报告

absi2011 posted @ Nov 21, 2015 01:41:29 AM in 刷题记录 with tags 模拟 CF Gym , 385 阅读

最近我在写非人类题目啊...

链接:http://codeforces.com/gym/100506/attachments/download/2760/20142015-ct-s02e06-codeforces-trainings-season-2-episode-6-en.pdf

题意:

给出若干个ACM队的成绩,求排名

特殊规则:

如果罚时都相同,那么考虑最大的X,使得两者可以得分情况不同(做出题目数或者罚时不同)

如果再相同那只好相同了...

解法:没啥好说的,暴力去

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct team
{
    string name;
    int ac[15];
    int unac[15];
    int ac_problems;
    int sum_time;
    friend bool operator < (const team &a,const team &b)
    {
        if (a.ac_problems!=b.ac_problems)
        {
            return a.ac_problems>b.ac_problems;
        }
        else if (a.sum_time!=b.sum_time)
        {
            return a.sum_time<b.sum_time;
        }
        else
        {
            int i;
            int aa=9,bb=9;
            int unsolved_a=0;
            int unsolved_b=0;
            int unget_time_a=0;
            int unget_time_b=0;
            for (i=300;i>=1;i--)
            {
                for (;aa>=0;)
                {
                    if (a.ac[aa]>i)
                    {
                        unsolved_a++;
                        unget_time_a+=a.ac[aa];
                        unget_time_a-=a.unac[aa]*20;
                        aa--;
                    }
                    else
                    {
                        break;
                    }
                }
                for (;bb>=0;)
                {
                    if (b.ac[bb]>i)
                    {
                        unsolved_b++;
                        unget_time_b+=b.ac[bb];
                        unget_time_b-=b.unac[bb]*20;
                        bb--;
                    }
                    else
                    {
                        break;
                    }
                }
                if (unsolved_a!=unsolved_b)
                {
                    return unsolved_a<unsolved_b;
                }
                else if (unget_time_a!=unget_time_b)
                {
                    return unget_time_a>unget_time_b;
                }
            }
        }
        return a.name<b.name;
    }
    friend bool operator > (const team &a,const team &b)
    {
        if (a.ac_problems!=b.ac_problems)
        {
            return a.ac_problems<b.ac_problems;
        }
        else if (a.sum_time!=b.sum_time)
        {
            return a.sum_time>b.sum_time;
        }
        else
        {
            int i;
            int aa=9,bb=9;
            int unsolved_a=0;
            int unsolved_b=0;
            int unget_time_a=0;
            int unget_time_b=0;
            for (i=300;i>=1;i--)
            {
                for (;aa>=0;)
                {
                    if (a.ac[aa]>i)
                    {
                        unsolved_a++;
                        unget_time_a+=a.ac[aa];
                        unget_time_a-=a.unac[aa]*20;
                        aa--;
                    }
                    else
                    {
                        break;
                    }
                }
                for (;bb>=0;)
                {
                    if (b.ac[bb]>i)
                    {
                        unsolved_b++;
                        unget_time_b+=b.ac[bb];
                        unget_time_b-=b.unac[bb]*20;
                        bb--;
                    }
                    else
                    {
                        break;
                    }
                }
                if (unsolved_a!=unsolved_b)
                {
                    return unsolved_a>unsolved_b;
                }
                else if (unget_time_a!=unget_time_b)
                {
                    return unget_time_a<unget_time_b;
                }
            }
        }
        return false;
    }
    void clear()
    {
        memset(ac,0,sizeof(ac));
        memset(unac,0,sizeof(unac));
        ac_problems=0;
        name="";
        sum_time=0;
    }
    void calc()
    {
        int i,j;
        for (i=0;i<10;i++)
        {
            for (j=i;j<10;j++)
            {
                if (ac[i]>ac[j])
                {
                    swap(ac[i],ac[j]);
                    swap(unac[i],unac[j]);
                }
            }
        }
    }
};
team a[105];
map<string,int> ma;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int zu;
    for (zu=0;zu<t;zu++)
    {
        ma.clear();
        int n,m;
        cin>>n>>m;
        int i;
        for (i=0;i<n;i++)
        {
            a[i].clear();
            cin>>a[i].name;
            ma[a[i].name]=i;
        }
        for (i=0;i<m;i++)
        {
            int time;
            string name;
            cin>>time;
            cin>>name;
            char prob;
            cin>>prob;
            string state;
            cin>>state;
            if (state=="rejected")
            {
                if (a[ma[name]].ac[prob-'A']>=1) continue;
                a[ma[name]].unac[prob-'A']--;
            }
            else
            {
                if (a[ma[name]].ac[prob-'A']>=1) continue;
                a[ma[name]].sum_time-=20*a[ma[name]].unac[prob-'A'];
                a[ma[name]].sum_time+=time;
                a[ma[name]].ac[prob-'A']=time;
                a[ma[name]].ac_problems++;
            }
        }
        for (i=0;i<n;i++)
        {
            a[i].calc();
        }
        sort(a,a+n);
        int rank=1;
        for (i=0;i<n;i++)
        {
            if ((i==0)||(a[i]>a[i-1]))
            {
                rank=i+1;
            }
            printf("%d %s %d %d\n",rank,a[i].name.c_str(),a[i].ac_problems,a[i].sum_time);
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter