CSES - KILO 2016 0/5 - Results
Submission details
Task:Elevator Trouble
Sender:Pekka Väänänen
Submission time:2016-09-06 15:43:45 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.74 sdetails
#4ACCEPTED0.06 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.71 sdetails
#7ACCEPTED0.66 sdetails
#8ACCEPTED0.10 sdetails
#9ACCEPTED0.07 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.31 sdetails
#12ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.sync_with_stdio(false);
    int floors, start, goal, u, d;
    cin >> floors >> start >> goal >> u >> d;

    set<int> visited;

    // each pair contains the current position and
    // also a set of all visited positions so we
    // can terminate the search when the current position
    // is already in the visited ones
    //queue<pair<int, set<int>>> to_visit;
    queue<pair<int, int>> to_visit;
    int shortest = -1;

    to_visit.push(make_pair(start, 0));

    while (to_visit.size() > 0) {
        // pop a pair from stack
        auto elem = to_visit.front();
        to_visit.pop();

        if (visited.count(elem.first)) {
            continue;
        }
        visited.insert(elem.first);
        // check if the current position is goal

        if (elem.first == goal) {
            // if it is, we are done
            //shortest = elem.second.size() + 1;
            shortest = elem.second;
            break;
        }

        // check if current position is invalid
        if (elem.first < 1 || elem.first > floors) {
            // if true, continue
            continue;
        }


        // check if the current position is already in the set
        /*if (elem.second.count(elem.first)) {
            // if it is, continue
            continue;
        }*/

        // create a new set for both children where the current position is added
        //set<int> newset = elem.second;
        //newset.insert(elem.first);

        // push the two child nodes
        to_visit.push(make_pair(elem.first + u, elem.second + 1));
        to_visit.push(make_pair(elem.first - d, elem.second + 1));
    }

    if (shortest == -1) {
        cout << "use the stairs\n";
    } else  {
        cout << shortest << "\n";
    }

}

Test details

Test 1

Verdict: ACCEPTED

input
10 1 10 2 1

correct output
6

user output
6

Test 2

Verdict: ACCEPTED

input
100 2 1 1 0

correct output
use the stairs

user output
use the stairs

Test 3

Verdict: ACCEPTED

input
1000000 1 1000000 1 1

correct output
999999

user output
999999

Test 4

Verdict: ACCEPTED

input
1000000 1 1000000 0 1

correct output
use the stairs

user output
use the stairs

Test 5

Verdict: ACCEPTED

input
1000000 1 1000000 0 0

correct output
use the stairs

user output
use the stairs

Test 6

Verdict: ACCEPTED

input
1000000 1 1000000 1 0

correct output
999999

user output
999999

Test 7

Verdict: ACCEPTED

input
1000000 1000000 1 0 1

correct output
999999

user output
999999

Test 8

Verdict: ACCEPTED

input
1000000 2 99999 2 1

correct output
50000

user output
50000

Test 9

Verdict: ACCEPTED

input
10 5 4 6 2

correct output
use the stairs

user output
use the stairs

Test 10

Verdict: ACCEPTED

input
1000000 1000000 1000000 100000...

correct output
0

user output
0

Test 11

Verdict: ACCEPTED

input
456789 2 456789 2 1

correct output
228395

user output
228395

Test 12

Verdict: ACCEPTED

input
100 50 51 4 6

correct output
use the stairs

user output
use the stairs