Editorial for CCC '15 J4 - Wait Time


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

by Patrick Au

The problem is asking you to measure the total time elapsed between messages.

Keep track of who is involved and the elapsed time while waiting. Make sure to output -1 if the number of messages sent exceeds the number messages received.

Time Complexity: \mathcal{O}(N)

Solution — C++

#include <bits/stdc++.h>

using namespace std;

vector<int> final(101);
vector<int> reply(101);
vector<int> sent(101);

void junior4(int m)
{
    char cmd;
    int n, t = 0;
    for(int i = 0; i < m; ++i)
    {
        cin >> cmd >> n;
        if(cmd == 'S')
        {
            final[n] += t - sent[n];
            reply[n] = 1;
        }
        else if(cmd == 'R')
        {
            reply[n] = -1;
            sent[n] = t;
        }
        else t += n - 2;
        t++;
    }
    for(int j = 0; j < 101; ++j)
    {
        if(reply[j])
        {
            if(reply[j] > 0)
                printf("%d %d\n", j, final[j]);
            else printf("%d %d\n", j, reply[j]);
        }
    }
}

int main()
{
    int m;
    scanf("%d", &m);
    junior4(m);
    return 0;
}

Comments

There are no comments at the moment.