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