The problem statement is here.

Problem Description

The task is to rank the contestants in the contest based on following criteria

  1. Contestants are ranked first by the number of problems solved (the more the better)
  2. then by decreasing amounts of penalty time
  3. If two or more contestants are tied in both problems solved and penalty time, they are displayed in order of increasing team numbers.

How Penalty time is calculated

Penalty time is computed as the number of minutes it took for the first correct submission for a problem to be received plus 20 minutes for each incorrect submission received prior to the correct solution.

The penalty time will be considered only if the problem is solved. There will not be any penalty if the problem is not solved even if the several Incorrect submissions were made. A problem is solved if any of the submissions for that problem is judged correct.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input consists of a snapshot of the judging queue, containing entries from some or all of contestants 1 through 100 solving problems 1 through 9. Each line of input will consist of three numbers and a letter in the format contestant problem time L

where L can be ‘C’, ‘I’, ‘R’, ‘U’ or ‘E’. These stand for Correct, Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do not affect scoring. Lines of input are in the order in which submissions were received.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output will consist of a scoreboard sorted as previously described. Each line of output will contain a contestant number, the number of problems solved by the contestant and the time penalty accumulated by the contestant. Since not all of contestants 1-100 are actually participating, display only the contestants that have made a submission.

Algorithm

for every test_case
    for every submission
        If a new contestant submitted a solution to a problem
            consider the user for the rest of the contest
            judge the solution to the problem
        else
            if the problem has not already been solved
                judge the solution to the problem

    calculate the penalty time for solved problems for every contestant
    print it

Data Structure

struct board

  • contestant: id of the contestant
  • nproblem: no of problem solved by the contestant
  • problem[1..9]: 1 if ith problem is solved by the contestant else 0
  • penalty[1..9]: total penalty time for the problem to be solved by contestant
  • time: total penalty time for whole contest awarded to the contestant

Any suggestions for improving efficiency or readability?

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

using namespace std;

struct board
{
  int contestant;
  int nproblem;
  int problem[10];
  int penalty[10];
  int time;
  board(int c): contestant(c), nproblem(0)
  {
    time = 0;
    for ( int i = 0; i < 10; ++i )
      {
    problem[i] = 0;
    penalty[i] = 0;
      }
  }
};

inline void init(int index[])
{
  for ( int i = 0; i < 101; ++i )
    index[i] = -1;
}

void judge(board &b, const int &problem, const int &time, const char &L)
{
  if ( L == 'C' )
    {
      ++b.nproblem;
      b.problem[problem] = 1;
      b.penalty[problem] += time;
    }
  else if ( L == 'I' )
    {
      b.penalty[problem] += 20;
    }
}

bool operator<(const board &b1, const board &b2)
{
  if ( b1.nproblem > b2.nproblem )
    return true;
  if ( b1.nproblem == b2.nproblem && b1.time < b2.time )
    return true;
  if ( b1.nproblem == b2.nproblem && b1.time == b2.time
       && b1.contestant < b2.contestant )
    return true;
  return false;
}

void calc_time(vector<board> &v)
{
  for ( vector<board>::iterator it = v.begin(); it != v.end(); ++it )
    {
      for ( int i = 1; i < 10; ++i )
    {
      if ( it->problem[i] == 1 )
        it->time += it->penalty[i];
    }
    }
}

int main()
{
  int T;
  string s;
  int contestant, problem, time;
  char L;

  cin >> T;
  getline(cin, s);
  getline(cin, s);
  for ( int t = 1; t <= T; ++t )
    {
      int index[101];
      init(index);
      vector<board> v;

      while( getline(cin, s) )
    {
      if ( s == "" ) break;

      istringstream iss(s);
      iss >> contestant >> problem >> time >> L;

      if ( index[contestant] == -1 )
        {
          v.push_back(*new board(contestant));
          index[contestant] = (int)v.size() - 1;
          judge(v[index[contestant]], problem, time, L);
        }
      else
        {
          if ( v[index[contestant]].problem[problem] == 0 )
        {
          judge(v[index[contestant]], problem, time, L);
        }
        }
    }
      calc_time(v);
      sort(v.begin(), v.end());
      for ( vector<board>::iterator it = v.begin(); it != v.end(); ++it )
    cout << it->contestant << ' ' << it->nproblem << ' ' << it->time << endl;
      if ( t < T )
    cout << endl;
    }
  return 0;
}

Refactored Code

The changes in the code is suggested by vnp

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

struct board
{
  int contestant;
  int nproblem;
  int problem[10];
  int penalty[10];
  int time;
  board(int c): contestant(c), nproblem(0)
  {
    time = 0;
    for ( int i = 0; i < 10; ++i )
      {
          problem[i] = 0;
          penalty[i] = 0;
      }
  }
  void calc_time()
  {
    for ( int i = 1; i < 10; ++i )
      {
          if ( problem[i] == 1 )
          time += penalty[i];
      }
  }
};

inline void init(int index[])
{
  for ( int i = 0; i < 101; ++i )
    index[i] = -1;
}

void judge(board &b, const int &problem, const int &time, const char &L)
{
  if (b.problem[problem] == 1)
    {
      return;
    }
  if ( L == 'C' )
    {
      ++b.nproblem;
      b.problem[problem] = 1;
      b.penalty[problem] += time;
    }
  else if ( L == 'I' )
    {
      b.penalty[problem] += 20;
    }
}

bool operator<(const board &b1, const board &b2)
{
  if ( b1.nproblem > b2.nproblem )
    return true;
  if ( b1.nproblem == b2.nproblem && b1.time < b2.time )
    return true;
  if ( b1.nproblem == b2.nproblem && b1.time == b2.time
       && b1.contestant < b2.contestant )
    return true;
  return false;
}

int main()
{
  int T;
  std::string s;
  int contestant, problem, time;
  char L;

  std::cin >> T;
  getline(std::cin, s);
  getline(std::cin, s);
  for ( int t = 1; t <= T; ++t )
    {
      int index[101];
      std::fill(index, index + 101, -1);
      std::vector<board> v;

      while( getline(std::cin, s) )
    {
      if ( s == "" ) break;

      std::istringstream iss(s);
      iss >> contestant >> problem >> time >> L;

      if ( index[contestant] == -1 )
        {
          v.push_back(*new board(contestant));
          index[contestant] = (int)v.size() - 1;
        }
      judge(v[index[contestant]], problem, time, L);
    }


      for ( std::vector<board>::iterator it = v.begin(); it != v.end(); ++it )
          it->calc_time();

      sort(v.begin(), v.end());
      for ( std::vector<board>::iterator it = v.begin(); it != v.end(); ++it )
          std::cout << it->contestant << ' ' << it->nproblem << ' ' << it->time << std::endl;
      if ( t < T )
          std::cout << std::endl;
    }
  return 0;
}
up vote 2 down vote accepted
  • The judgement is split into two unrelated fragments: the judge function and the v[index[contestant]].problem[problem] == 0 test. Looking at judge() it is very hard to say that submissions are handled correctly.

    I recommend to consolidate judgement in a single place:

    void judge(board &b, const int &problem, const int &time, const char &L)
    {
        if (b.problem[problem] == 1) {
            return;
        }
        if ( L == 'C' ) {
            ++b.nproblem;
            b.problem[problem] = 1;
            b.penalty[problem] += time;
        } else if ( L == 'I' ) {
            b.penalty[problem] += 20;
        }
    }
    

    and relieve the main loop from any judgement:

        if (index[contestant] == -1) {
            v.push_back(*new board(contestant));
            index[contestant] = (int)v.size() - 1;
        }
        judge(v[index[contestant]], problem, time, L);
    
  • Computation of a contestant's total penalty definitely should be a board member function.

  • init is not a very meaningful name. Also consider replacing it with

    std::fill(index, index + 101, -1);
    
  • If features are available, change for loops to range-based:

    for (auto it: v)
    
  • Avoid using namespace std;

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.