oj.uz

Submission #425838

# Submission time Handle Problem Language Result Execution time Memory
425838 2021-06-13T11:51:37 Z Artix Rail (IOI14_rail) C++14
30 / 100
 96 ms 1616 KB 
    #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() or 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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 1616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 1540 KB Output isn't correct
2 Halted 0 ms 0 KB -