PKU 1030 Rating

Rating

問題文の通りに実装。面倒。

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    //  Input
    const int N = 101;
    vector<vector<int> > team( N, vector<int>(2,-1) );

    for ( int i=0; i<2; i++ )
    {
        int n;  cin >> n,  cin.ignore();
        int rank = 1;
        for ( int j=0; j<n; j++ )
        {
            string l;  getline( cin, l );
            stringstream ss(l);
            int t, c = 0;
            while ( ss >> t )
                team[t][i] = rank,  c++;
            rank += c;
        }
    }

    //  Rate the teams participated twice
    vector<vector<int> > overall;

    for ( int i=0; i<N; i++ )
    if ( team[i][0] >= 0  &&  team[i][1] >= 0 )
    {
        bool f = false;

        for ( int j=0; j<(int)overall.size() && !f; j++ )
            if ( team[i][0] + team[i][1]
                    == team[overall[j][0]][0] + team[overall[j][0]][1] )
                overall[j].push_back( i ),
                f = true;

        for ( int j=0; j<=(int)overall.size() && !f; j++ )
            if ( j == (int)overall.size()  ||
                 team[i][0] + team[i][1]
                    < team[overall[j][0]][0] + team[overall[j][0]][1] )
                overall.insert( overall.begin()+j, vector<int>(1,i) ),
                f = true;
    }

    //  Rate the teams participated once
    for ( int i=0; i<N; i++ )
    if ( team[i][0] < 0  &&  team[i][1] >= 0  ||
         team[i][0] >= 0  &&  team[i][1] < 0 )
    {
        //  rule A
        vector<int> cand;
        for ( int j=0; j<(int)overall.size(); j++ )
            for ( int k=0; k<(int)overall[j].size(); k++ )
            if ( team[overall[j][k]][0] >= 0  &&  team[overall[j][k]][1] >= 0 )
                if ( team[overall[j][k]][0] == team[i][0]  ||
                     team[overall[j][k]][1] == team[i][1] )
                {
                    cand.push_back( j );
                    break;
                }
        if ( (int)cand.size() == 1 )
            overall[cand[0]].push_back( i );

        //  rune B
        if ( cand.empty() )
        {
            int mn = -1;
            for ( int j=0; j<(int)overall.size(); j++ )
                for ( int k=0; k<(int)overall[j].size(); k++ )
                if ( team[overall[j][k]][0] >= 0  &&  team[overall[j][k]][1] >= 0 )
                    if ( team[i][0] >= 0  &&  team[overall[j][k]][0] < team[i][0]  ||
                         team[i][1] >= 0  &&  team[overall[j][k]][1] < team[i][1] )
                        mn = j;
            
            int mx = (int)overall.size();
            for ( int j=(int)overall.size()-1; j>=0; j-- )
                for ( int k=0; k<(int)overall[j].size(); k++ )
                if ( team[overall[j][k]][0] >= 0  &&  team[overall[j][k]][1] >= 0 )
                    if ( team[i][0] >= 0  &&  team[overall[j][k]][0] > team[i][0]  ||
                         team[i][1] >= 0  &&  team[overall[j][k]][1] > team[i][1] )
                        mx = j;
            
            if ( mx - mn >= 1 )
            {
                bool f = false;

                for ( int j=mn+1; j<mx && !f; j++ )
                {
                    if ( team[overall[j][0]][0]+team[overall[j][0]][1]
                         == team[i][0] + team[i][1] )
                        overall[j].push_back( i ),
                        f = true;
                    else if ( team[overall[j][0]][0]+team[overall[j][0]][1]
                              > team[i][0] + team[i][1] )
                        overall.insert( overall.begin()+j, vector<int>(1,i) ),
                        f = true;
                }
                if ( ! f )
                    overall.insert( overall.begin()+mx, vector<int>(1,i) );
            }           
        }
    }

    //  Output
    for ( int i=0; i<(int)overall.size(); i++ )
    {
        sort( overall[i].begin(), overall[i].end() );
        for ( int j=0; j<(int)overall[i].size(); j++ )
            cout << (j>0?" ":"") << overall[i][j];
        cout << endl;
    }

}