10901 - Ferry Loading III

[predator]

i am having a difficulty in understanding the statement of the problem. can any one please explain me the 2nd sample

[Martin Macko]

i am having a difficulty in understanding the statement of the problem. can any one please explain me the 2nd sample

At the begining the ferry is on the left bank waiting for a car. In 10 minutes a car arrives to the right bank while there is no car on the left bank at that time. Therefore, the ferry heads for the right bank. It arrives there at 20, loads the car and returns back to the left bank. After returning (at 30) it unloads the first car and loads the second one, as it has already come (at 25). Further it travels to the right bank, unloads the second car (at 40) and returns back on the left bank (at 50), again, where it loads the last car and deliver it to the right bank at 60.

[sclo]

remember that the ith output is the exit time of the ith car, and the exit times are not necessarily sorted in nondecreasing time.

[RED-C0DE]

Please give me some Sample IO For this Problem... my program worked correctly with many IO samples...but WA...

tanks

[ljacs]

Please help.

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <stack>
#include <queue>
typedef unsigned long long ll;
using namespace std;

queue<int> l;
queue<int> r;

int main()
{
    int c; scanf("%d", &c);
    while (c--){
        int n,t,m;
        scanf("%d %d %d", &n, &t, &m);
        bitset<10000> posicoes;
        vector<int> listaL, listaR;
        posicoes.reset();
        int indice = 0;
        for (int i = 0; i<m; i++){
            int time; char side[10];
            scanf("%d %s", &time, side);
            if (side[0]=='l'){
                l.push(time);
            } else {
                r.push(time);
                posicoes[indice++] = true;
            }
        }
        
        int atual = 0;
        int carga;
        bool side = false;
        // false = left
        // true = right
        while (!l.empty() || !r.empty()){
            if (!l.empty() && !r.empty()) {
                if(l.front() > atual && r.front() > atual) {
                    if(l.front() > r.front()) {
                        atual += r.front() - atual;
                        if(!side) atual += t;
                        side = true;
                    }
                    else {
                        atual += l.front() - atual;
                        if(side) atual += t;
                        side = false;
                    }
                }
            } else {
                if (l.empty()) {
                    if (r.front() > atual) {
                        atual += r.front() - atual;
                        if(!side) atual += t;
                        side = true;
                    }
                }
                else {
                    if (l.front() > atual) {
                        atual += l.front() - atual;
                        if(side) atual += t;
                        side = false;
                    }
                }
            }
            if (!side) {
                carga = 0;
                while (carga < n && !l.empty() && l.front() <= atual) {
                    listaL.push_back(atual+t);
                    l.pop();
                    carga++;
                }
                atual += t;
                side = true;
            }
            else {
                carga = 0;
                while (carga < n && !r.empty() && r.front() <= atual) {
                    listaR.push_back(atual+t);
                    r.pop();
                    carga++;
                }
                atual += t;
                side = false;
            }
        }
        
        int indr=0, indl=0;
        for (int i = 0; i<m; i++){
            if (posicoes[i]){
                printf("%d", listaR[indr++]);
            } else printf("%d", listaL[indl++]);
            printf("\n");
        }
        if (c>0) printf("\n");
        listaL.clear();
        listaR.clear();
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

1
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right

Correct output:

Code: Select all

5
15
15
15
25
10
20

[Mukit Chowdhury]

Input:

Code: Select all

1
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right

Correct output:

Code: Select all

5
15
15
15
25
10
20

@brianfry713... is it legal that arrival times are same ??? In arrival time 5 ,if a cargo comes in left bank,how at the same times another cargo can come in right bank ??? the problem statement says... " The arrival times for each test case are strictly increasing...."
I am really confused ... please help !!!

[brianfry713]

Read this entire thread. Your question has already been answered by the problem setter.

[Mukit Chowdhury]

Read this entire thread. Your question has already been answered by the problem setter.

Thanks a lot brianfry713.... for your quick reply...
It's my fault....

[Mukit Chowdhury]

Got WA !!! Help please !!!

Code: Select all

Accepted......

Sorry for my bad coding...

[brianfry713]

For input:

Code: Select all

1
1 5 2
0 left
0 left

My AC code prints:

Code: Select all

5
15

Instead of using a map, I just keep track of the finish times of the left and right queues, and the order of which side each input was.

[Mukit Chowdhury]

For input:

Code: Select all

1
1 5 2
0 left
0 left

My AC code prints:

Code: Select all

5
15

Instead of using a map, I just keep track of the finish times of the left and right queues, and the order of which side each input was.

I haven't understood what have you done... but I have used 4 queue this time... two are for value keeping and two are for index keeping of that values... would you give me some critical input for my code,please ???

Code: Select all

Accepted .........

[Mukit Chowdhury]

for input...

Code: Select all

7
1 5 2
0 right
0 left
2 5 2
0 left
0 left
2 5 2
0 right
0 right
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
1 5 2
0 right
1 left
2 5 2
0 right
6 right
2 5 2
0 right
5 right

my codes shows...

Code: Select all

10
5

5
5

10
10

5
15
15
15
25
10
20

10
15

10
20

10
10

These are correct,right ???

[brianfry713]

You can generate I/O at http://www.uvatoolkit.com/problemssolve.php

[Mukit Chowdhury]

I tried there but haven't found any error ...
So I thought if you can find any bug seeing my code by your experience & can give me some critical input...
Would you,please?