Submission #425835

#	Time	Username	Problem	Language	Result	Execution time	Memory
425835		Artix	Rail (IOI14_rail)	C++14	30 / 100	97 ms	1660 KiB

rail

    #include <bits/stdc++.h>
    #include "rail.h"
     
    template <class T>
    using Vec = std::vector<T>;
     
    int dist(const int i, const int j) {
        if (i == j) return 0;
        if (i > j) return dist(j, i);
        static std::map<std::pair<int, int>, int> memo;
        auto& val = memo[{i, j}];
        if (val == 0) {
            val = getDistance(i, j);
        }
        return val;
    }
     
    void findLocation(int n, int first, int location[], int stype[]) {
        location[0] = first;
        stype[0] = 1;
        Vec<std::pair<int, int>> order;
        order.reserve(n - 1);
        for (int i = 1; i < n; ++i) {
            order.emplace_back(dist(0, i), i);
        }
        std::sort(order.begin(), order.end());
        int l = 0, r = order[0].second;
        location[r] = location[l] + order[0].first;
        stype[r] = 2;
        order.erase(order.begin());
        std::map<int, int> idx;
        idx[location[l]] = l;
        idx[location[r]] = r;
        for (const auto [d_0, i]: order) {
            const auto d_l = dist(l, i); 
            const auto d_r = dist(r, i);
            const auto m = ((location[l] + d_l) + (location[r] - d_r)) / 2;
            if ((idx.find(m) != idx.end() and stype[idx[m]] == 1)) {
                location[i] = location[l] + d_l;
                stype[i] = 2;
                if (location[r] < location[i]) {
                    r = i;
                }
            }
            else {
                location[i] = location[r] - d_r;
                stype[i] = 1;
                if (location[i] < location[l]) {
                    l = i;
                }
            }
            idx[location[i]] = i;
        }
    }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:34:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for (const auto [d_0, i]: order) {
      |                         ^

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