gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

ACM-ICPC 「ICPCの順位づけ」 解説

問題
ICPC Ranking | Aizu Online Judge

解説
少し考えることが多いのですが、とりあえず
・tim: 各チームの所要時間を格納する1次元int配列
・solve :各チームの各問題の解けたかどうかを格納する2次元bool配列
 →solve[チーム番号][問題番号]=true or false で管理
・WA: 各チームの各問題を何回間違えたかを格納する2次元int配列

は要りそうなので、これらを使ってうまくやる方針で解きました。
solveで問題の解答状況を保存した後、各チームが合計で何問解けたかを算出します。
この時に、ついでに間違えた数*20のペナルティも扱います。

必要な数字を揃えれば、あとはソートをすれば終わりです。
pairに入れることで、first要素を優先してソートし、firstが同じ時はsecondで判定します。今回はこれを入れ子にすることで3つの値を扱います。

また、問題数は多い順に順位が高く、解答時間は短いほうが良いです。つまり、ソートするにしても「昇順」か「降順」かが異なります。今回はまとめて昇順ソートするので、降順にしたいものについてはマイナスをかけることで対処しました。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
//typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    int M,T,PP,R;
    while(cin>>M>>T>>PP>>R && M){
        vector<int> tim(T,0); //各チームの所用時間
        vector<vector<bool>> solve(T,vector<bool>(PP,false)); //チームごとに各問題が解けたかどうかをboolで
        vector<vector<int>> WA(T,vector<int>(PP,0)); //チームごとに各問題を何回間違えたか
    
        rep(i,0,R){
            int m,t,p,r;
            cin>>m>>t>>p>>r;
            t--; p--; 
            if(r==0){ //正解したら、その時のmを足してとsolveをtrueに
                solve[t][p]=true;  
                tim[t]+=m;   
            }
            else WA[t][p]++; //間違えたらWAを増やす
        }
    
        vector<int> solve_count(T,0); //チームごとに結局何問正解できたか
        //2重forで数えます
        rep(i,0,T){
            rep(j,0,PP){
                if(solve[i][j]){
                    solve_count[i]++;
                    tim[i]+=WA[i][j]*20;   
                }
            }
        }
        vector<pair<int,pair<int,int>>> rank; //いよいよソートします。この配列は3つの値を持ち、<問題数、時間、チーム番号>で格納。
        /*ソート自体は昇順で行いますが、問題数は降順、時間は昇順、チーム番号は降順でソートしたいので、
        降順にしたいものにはマイナスをつけることで対処します。これにより、元の値が大きいほど値が小さくなるのでうまくいきます。
        */
        rep(i,0,T){
            rank.pb(MP(-solve_count[i],MP(tim[i],-(i+1))));
        }
        Sort(rank);
        
        /*rep(i,0,T){
            cout<<rank[i].fi<<" "<<rank[i].se.fi<<" "<<-rank[i].se.se<<endl;
        }*/
        
        //最後に出力です。出力するものはrank[].se.seだけですが、マイナスをつけて格納しているのでマイナスをつけて出力します。
        rep(i,0,T){
            if(i)cout<<",";
            cout<<-rank[i].se.se;
            while(i+1<T && rank[i].fi==rank[i+1].fi && rank[i].se.fi==rank[i+1].se.fi){
                i++;
                cout<<"=";
                cout<<-rank[i].se.se;
            }
        }
        cout<<endl;
    }
    
    return 0;
}