10901 - Ferry Loading III

[lbv]

getting TLE....
Help need ...

You may try these cases:

Input

Code: Select all

2
2 24 7
2 right
7 left
12 right
22 right
34 right
73 right
76 right
4 3 8
5102 left
8090 right
9875 left
14954 left
19584 right
31434 left
76546 left
77138 left

Output

Code: Select all

50
74
50
98
98
146
146

5105
8093
9878
14960
19587
31437
76552
77144

[Munchor]

Code: Select all

2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left
2 10 3
10 right
25 left
40 left
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
2 24 7
2 right
7 left
12 right
22 right
34 right
73 right
76 right

I get all those cases correct. However, I get these two wrong:

Code: Select all

1 10 3
0 left
10 right
30 left
4 3 8
5102 left
8090 right
9875 left
14954 left
19584 right
31434 left
76546 left
77138 left

Correct output

Code: Select all

10
20
40

5105
8093
9878
14960
19587
31437
76552
77144

My output

Code: Select all

10
20
50

8099
8096
9881
14960
31443
31440
76552
77144

So I'm not that far away, I'm doing something wrong and I can't find out what, here's my full code:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

struct boat
{
  int arrival_time;
  int final_time;
  int index;
};

int cases, n, t, m, i, v, time, new_boat_time, boats_carrying;
bool left_side;
char side[6];
queue<boat> right, left;
vector<boat> output;

void read_input()
{
  scanf("%d %d %d", &n, &t, &m);

  output.clear();
  
  for (i = 0; i < m; i++)
  {
    scanf("%d %s", &new_boat_time, side);

    boat new_boat;
    new_boat.arrival_time = new_boat_time;
    new_boat.final_time = 0;
    new_boat.index = (int) output.size();

    if (strcmp(side, "right") == 0)
    {
      right.push(new_boat);
    }
    else
    {
      left.push(new_boat);
    }
    
    output.push_back(new_boat);
  }
}

int main()
{
  scanf("%d", &cases);

  for (v = 0; v < cases; v++)
  {
    read_input();
    left_side = true;
    time = 0;

    while (!(right.empty() && left.empty()))
    {
      boats_carrying = 0;

      if (left_side)
      {
        for (i = 0; i < n; i++)
        {
          if (!left.empty())
          {
            if (left.front().arrival_time <= time)
            {
              //printf("%d\n", time + t);
              output[left.front().index].final_time = time + t;
              left.pop();
              boats_carrying++;
            }
          }
        }

        if (boats_carrying > 0)
        {
          time += t;
        }
        else
        {
          if (right.front().arrival_time > time)
          {
            time += t + right.front().arrival_time - time;
          }
          else
          {
            time += t;
          }
        }
      }
      else
      {
        for (i = 0; i < n; i++)
        {
          if (!right.empty())
          {
            if (right.front().arrival_time <= time)
            {
              //printf("%d\n", time + t);
              output[right.front().index].final_time = time + t;
              right.pop();
              boats_carrying++;
            }
          }
        }

        if (boats_carrying > 0)
        {
          time += t;
        }
        else
        {
          if (left.front().arrival_time > time)
          {
            time += t + left.front().arrival_time - time;
          }
          else
          {
            time += t;
          }
        }
      }

      left_side = !left_side;
    }

    for (i = 0; i < (int) output.size(); i++)
    {
      printf("%d\n", output[i].final_time);
    }
    
    if (v != cases - 1)
    {
      printf("\n");
    }
  }

  return 0;
}

[a.elbashandy]

I passed all the test cases and it still got WA, can anyone please help me ?

Code: Select all

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    int T; scanf("%d", &T);
    while(T--){
        queue< pair<int, int> > leftQ, rightQ;
        int n, t, m;
        scanf("%d %d %d", &n, &t, &m);
        
        char buff[10];
        int z;
        string s;
        vector<int> v;
        for (int i = 0; i < m; i++) {
            scanf("%d %s", &z, buff);
            s = buff;
            if(s == "left")
                leftQ.push(make_pair(z, i));
            else
                rightQ.push(make_pair(z, i));
            v.push_back(0);
        }
        
        int totalTime = 0;
        bool left = true;
        bool first = true;
        while(!leftQ.empty() || !rightQ.empty()){           
            
            if(left && !leftQ.empty()){
                int k = 0;
                totalTime += t;
                for (int i = 0; i < n; i++) {
                    int a = leftQ.front().first;
                    if((totalTime-t) >= a && !leftQ.empty()) k++;
                    else break;
                    v[leftQ.front().second] = totalTime;
                    //printf("%d\n", totalTime);
                    leftQ.pop();
                }
                
                if(!k){
                    if(!rightQ.empty() && rightQ.front().first < leftQ.front().first) totalTime += abs((totalTime-t) - rightQ.front().first);
                    else{
                        int a = leftQ.front().first;
                        int x = a;
                        if((totalTime-t) < a) 
                            totalTime += a - (totalTime-t);
                        v[leftQ.front().second] = totalTime;
                        //printf("%d\n", totalTime);
                        leftQ.pop();
                        for (int i = 1; i < n && !leftQ.empty(); i++) {
                            a = leftQ.front().first;
                            if(a > x) break;
                            v[leftQ.front().second] = totalTime;
                            //printf("%d\n", totalTime);
                            leftQ.pop();
                            if(leftQ.empty()) break;
                        }
                    }
                }                                
                left = false;
            }else if(!left && !rightQ.empty()){
                int k = 0;
                totalTime += t;
                for (int i = 0; i < n; i++) {
                    int a = rightQ.front().first;
                    if((totalTime-t) >= a && !rightQ.empty()) k++;
                    else break;
                    v[rightQ.front().second] = totalTime;
                    //printf("%d\n", totalTime);
                    rightQ.pop();
                }
                
                if(!k){
                    if(!leftQ.empty() && leftQ.front().first < rightQ.front().first) totalTime += abs((totalTime - t) - leftQ.front().first);
                    else{
                        int a = rightQ.front().first;
                        int x = a;
                        if((totalTime-t) < a) totalTime += a - (totalTime-t);
                        v[rightQ.front().second] = totalTime;
                        //printf("%d\n", totalTime);
                        rightQ.pop();
                        for (int i = 1; i < n && !rightQ.empty(); i++) {
                            a = rightQ.front().first;
                            if(a > x) break;
                            v[rightQ.front().second] = totalTime;
                            //printf("%d\n", totalTime);
                            rightQ.pop();
                            if(rightQ.empty()) break;
                        }
                    }
                        
                }
                left = true;
            }else{
//                totalTime += t;
//                left = (left) ? false: true;
                if(left && !rightQ.empty()){
                    if(totalTime < rightQ.front().first){
                        totalTime += abs(totalTime - rightQ.front().first) + t;
                    }else{
                        totalTime += t;
                    }
                    left = false;
                }else if(!left && !leftQ.empty()){
                    if(totalTime < leftQ.front().first){
                        totalTime += abs(totalTime - leftQ.front().first) + t;
                    }else{
                        totalTime += t;
                    }
                    left = true;
                }
            }
        }
        
        for (int i = 0; i < v.size(); i++) {
            printf("%d\n", v[i]);
        }

        
        if(T) printf("\n");
    }
    return 0;
}

[brianfry713]

Munchor, for input:

Code: Select all

1 10 3
0 left
10 right
30 left

Correct output

Code: Select all

10
20
40

Your output

Code: Select all

10
20
50

At time 20 the ferry is at the left bank and no cars are waiting so it shouldn't move. At time 30 when the car arrives at the left bank it should be transported to the right bank. I'm guessing your code has the empty ferry moving to the right bank at time 20.

a.elbashandy, it looks like you figured it out.

[cyberdragon]

Why WA ?
http://ideone.com/AQnsSi

[brianfry713]

Input:

Code: Select all

1
1 5 2
0 left
0 left

AC output:

Code: Select all

5
15

[cyberdragon]

"The arrival times for each test case are strictly increasing."
This case is invalid.

[brianfry713]

There is a case in the judge's input where two consecutive arrival times are equal. The problem statement should actually say non-decreasing instead of strictly increasing.

[doried_a_a]

Hello every body,
this problem made me go crazy!
here is my code, which passed all the test given by this thread as (correct tests).

Code: Select all

AC! without changing my code!!! 

I've noticed that UVa toolkit dosen't produce correct output!
Please, Help!!!!

[sith]

Hi

could somebody explain why this input

Code: Select all

1
2 2 1
3 right

produces result

Code: Select all

7

If ferry starts from the left bench, it should stay there as there are no cars on either of banks until 3. after it it will take 1 to get to the right bank and 1 to travel back. So it should be 5.

Why is it 7?