Robotti

#include <iostream>
#include <string>
#include <vector>
 
int main() {
    unsigned long totalMove{0};
    long totalCoins{0};
 
    // Tämä on tässä koodissa oikeastaan turha, koska voisin vain käyttää
    // .length():iä ennemminkin.
    long roomAmount;
    std::cin >> roomAmount;
 
    std::string rooms;
    std::cin >> rooms;
 
    // Testaukseen suurilla luvuilla
    /*auto startTime { std::chrono::high_resolution_clock::now() };
    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());*/
 
    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) };
 
    auto firstCoin{ coinPositions.begin() };
    auto lastCoin{ coinPositions.end() };
 
    while (totalCoins < maxCoins) {
 
 
        auto nearestCoin = std::lower_bound(firstCoin, lastCoin, currentPos);
        auto pluslength{ (nearestCoin != lastCoin) ? *nearestCoin - currentPos : 0 };
        auto minuslength{ (nearestCoin != firstCoin) ? currentPos - *(std::prev(nearestCoin)) : 0 };
 
        if (pluslength == minuslength) break;
            // Tässä saattaa olla turhan paljon toistoa, mutta ainakin toimii
        else if (pluslength != 0 && (pluslength < minuslength || minuslength <= 0)) {
            currentPos += pluslength;
            coinPositions.erase(nearestCoin);
            totalMove += pluslength;
            ++totalCoins;
        } else {
            currentPos -= minuslength;
            coinPositions.erase(std::prev(nearestCoin));
            totalMove += minuslength;
            ++totalCoins;
        }
    }
    std::cout << totalMove << " " << totalCoins << std::endl;
 
    // 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: ACCEPTED

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: ACCEPTED

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: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: ACCEPTED