Robotti

#include <iostream>
#include <string>
#include <vector>
#include <climits>
 
int main() {
    unsigned long totalMove{0};
    long totalCoins{0};
 
    long roomAmount;
    std::cin >> roomAmount;
 
    std::string rooms;
    std::cin >> rooms;
 
    // Testaukseen suurilla luvuilla
    /*std::string jono;
    //jono.reserve(roomAmount);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution charDist(0, 3);
    for (long i = 0; i < 199999; ++i) {
        char nextChar = ".***"[charDist(gen)];
        jono += nextChar;
    }
    std::uniform_int_distribution startLoc(0, 199999);
    jono[startLoc(gen)] = 'R';
    std::string rooms{jono};
    auto roomAmount = static_cast<long>(rooms.length());
    auto startTime { std::chrono::high_resolution_clock::now() };*/
 
    long maxCoins{0};
    std::vector<long> coinPositions;
    for (auto i = 0; i < roomAmount; ++i) {
        if (rooms[i] == '*') {
            ++maxCoins;
            coinPositions.push_back(i);
        }
    }
 
    auto startPos{ rooms.find('R') };
    auto currentPos{ static_cast<long>(startPos) };
 
    const auto firstCoin{ coinPositions.begin() };
    const auto lastCoin{ coinPositions.end() };
 
    while (totalCoins < maxCoins) {
        auto nearestCoin = std::lower_bound(firstCoin, lastCoin, currentPos);
        int goingOvers = 1;
 
        while (nearestCoin != lastCoin && *nearestCoin == LONG_MAX) {
            ++nearestCoin;
            ++goingOvers;
        }
 
        auto pluslength{ (nearestCoin != lastCoin) ? *nearestCoin - currentPos : 0 };
        auto minuslength{ (nearestCoin != firstCoin) ? currentPos - *(nearestCoin - goingOvers) : 0 };
 
        if (pluslength != 0 && (pluslength < minuslength || minuslength <= 0)) {
            currentPos += pluslength;
            *nearestCoin = LONG_MAX;
            totalMove += pluslength;
            ++totalCoins;
        } else if (pluslength != minuslength) {
            currentPos -= minuslength;
            *(nearestCoin - goingOvers) = LONG_MAX;
            totalMove += minuslength;
            ++totalCoins;
        } else break;
    }
 
    std::cout << totalMove << " " << totalCoins << "\n";
 
    // Testaukseen
    /*auto endTime{std::chrono::high_resolution_clock::now()};
    auto duration{std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime)};
    int durationInt = static_cast<int>(duration.count());
    std::cout << durationInt << "\n";*/
    // Syötteen esimerkki omaa muistia varten: **.*......*.R*...*..
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: RUNTIME ERROR

munmap_chunk(): invalid pointer

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 1, 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: RUNTIME ERROR

munmap_chunk(): invalid pointer

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: RUNTIME ERROR

munmap_chunk(): invalid pointer

Test 19

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: RUNTIME ERROR

malloc(): invalid next size (unsorted)

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED