Submission #977392

#	Time	Username	Problem	Language	Result	Execution time	Memory
977392		totoro	Rail (IOI14_rail)	C++17	100 / 100	56 ms	1060 KiB

rail

// SOLVED   SUBTASK 1 (08 pts)
// SOLVED   SUBTASK 2 (22 pts)
// SOLVED   SUBTASK 3 (26 pts)
// SOLVED   SUBTASK 4 (44 pts)
// [+-+]----------------------
// TOTAL    100/100 pts

#include "rail.h"

#include <functional>
#include <queue>
#include <vector>

struct Station {
    int distanceFromZero;
    int index;

    Station(int distanceFromZero, int index) : distanceFromZero(distanceFromZero), index(index) {}

    friend bool operator<(const Station& a, const Station& b) {
        return a.distanceFromZero > b.distanceFromZero;
    }
};

typedef int idx;

void findLocation(int N, int first, int location[], int stype[]) {
    location[0] = first;
    stype[0] = 1;

    std::priority_queue<Station> stationsQueue;
    for (size_t i = 1; i < N; ++i) {
        stationsQueue.push(Station(getDistance(0, i), i));
    }

    // -------------------------------------------
    // Right stations
    // -------------------------------------------
    std::vector<int> typeDDistances;
    Station furthestRight = stationsQueue.top();
    stationsQueue.pop();
    location[furthestRight.index] = furthestRight.distanceFromZero + first;
    stype[furthestRight.index] = 2;
    typeDDistances.push_back(furthestRight.distanceFromZero);
    std::queue<Station> leftStations;
    while (!stationsQueue.empty()) {
        Station nextClosest = stationsQueue.top();
        stationsQueue.pop();
        int distanceFromFurthestRight = getDistance(furthestRight.index, nextClosest.index);
        bool found = false;
        for (int r = typeDDistances.size() - 1; r >= 0; --r) {
            int distanceFromR = distanceFromFurthestRight - (furthestRight.distanceFromZero - typeDDistances[r]);
            if (nextClosest.distanceFromZero == typeDDistances[r] + distanceFromR) {
                if (distanceFromR < typeDDistances[r]) {
                    // It's a type C station to the right of 0
                    location[nextClosest.index] = furthestRight.distanceFromZero + first - distanceFromFurthestRight;
                    stype[nextClosest.index] = 1;
                } else {
                    // It's to the left of 0
                    leftStations.push(nextClosest);
                }
                found = true;
                break;
            }
        }
        if (!found) {
            // It's a new furthestRight
            furthestRight = nextClosest;
            location[furthestRight.index] = furthestRight.distanceFromZero + first;
            stype[furthestRight.index] = 2;
            typeDDistances.push_back(furthestRight.distanceFromZero);
        }
    }

    // -------------------------------------------
    // Left stations
    // -------------------------------------------
    if (leftStations.empty()) {
        return;
    }
    std::vector<int> typeCDistances;
    Station furthestLeft = leftStations.front();
    leftStations.pop();
    location[furthestLeft.index] = first - (furthestLeft.distanceFromZero - 2 * typeDDistances[0]);
    stype[furthestLeft.index] = 1;
    typeCDistances.push_back(furthestLeft.distanceFromZero);
    while (!leftStations.empty()) {
        Station nextClosest = leftStations.front();
        leftStations.pop();
        int distanceFromFurthestLeft = getDistance(furthestLeft.index, nextClosest.index);
        bool found = false;
        for (int l = typeCDistances.size() - 1; l >= 0; --l) {
            int distanceFromL = distanceFromFurthestLeft - (furthestLeft.distanceFromZero - typeCDistances[l]);
            if (nextClosest.distanceFromZero == typeCDistances[l] + distanceFromL) {
                // It's a type D station to the left of 0
                location[nextClosest.index] = first - (furthestLeft.distanceFromZero - 2 * typeDDistances[0]) + distanceFromFurthestLeft;
                stype[nextClosest.index] = 2;
                found = true;
                break;
            }
        }
        if (!found) {
            // It's a new furthestLeft
            furthestLeft = nextClosest;
            location[furthestLeft.index] = location[furthestLeft.index] = first - (furthestLeft.distanceFromZero - 2 * typeDDistances[0]);
            stype[furthestLeft.index] = 1;
            typeCDistances.push_back(furthestLeft.distanceFromZero);
        }
    }

    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:32:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |     for (size_t i = 1; i < N; ++i) {
      |                        ~~^~~
rail.cpp:105:42: warning: operation on '*(location + ((sizetype)(((long unsigned int)furthestLeft.Station::index) * 4)))' may be undefined [-Wsequence-point]
  105 |             location[furthestLeft.index] = location[furthestLeft.index] = first - (furthestLeft.distanceFromZero - 2 * typeDDistances[0]);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44