oj.uz

Submission #700691

# Submission time Handle Problem Language Result Execution time Memory
700691 2023-02-19T08:18:17 Z Cyanmond Rail (IOI14_rail) C++17
100 / 100
 297 ms 98896 KB 
#include "rail.h"
#include <bits/stdc++.h>

void findLocation(int N, int first, int location[], int stype[]) {
    stype[0] = 1;
    location[0] = first;
    if (N == 1) {
        return;
    }
    std::vector<std::vector<int>> dists(N, std::vector<int>(N, -1));
    auto dist = [&](const int a, const int b) {
        assert(0 <= a and 0 <= b and a < N and b < N);
        if (a == b) {
            return 0;
        }
        if (dists[a][b] != -1) {
            return dists[a][b];
        }
        return dists[a][b] = dists[b][a] = getDistance(a, b);
    };

    std::vector<int> lkOrder(N);
    std::iota(lkOrder.begin(), lkOrder.end(), 0);
    std::sort(lkOrder.begin(), lkOrder.end(), [&](const int a, const int b) {
        return dist(0, a) < dist(0, b);
    });
    assert(lkOrder[0] == 0);
    const int sR = lkOrder[1];
    stype[sR] = 2;
    location[sR] = location[0] + dist(0, sR);

    std::vector<int> dRights, cLefts;
    std::unordered_set<int> used;
    used.insert(location[0]);
    used.insert(location[sR]);
    dRights.push_back(sR);
    bool fin = false;

    for (int i = 2; i < N; ++i) {
        const int v = lkOrder[i];
        bool isLeft = dist(0, v) == (dist(sR, v) + dist(0, sR));
        if (isLeft) {
            const int d = dist(sR, v);
            if (d < dist(0, sR)) {
                cLefts.push_back(v);
                location[v] = location[sR] - d;
                stype[v] = 1;
                used.insert(location[v]);
                continue;
            } else if (not fin) {
                cLefts.push_back(0);
                fin = true;
            }
            std::vector<int> pos;
            for (const int p : cLefts) {
                const int posA = location[p];
                const int posB = posA + (d - dist(sR, p));
                if (posB < location[0] and used.find(posB) == used.end()) {
                    pos.push_back(posB);
                }
            }

            const int b = cLefts.back();
            const int f1 = location[b] + dist(b, v);
            if (std::find(pos.begin(), pos.end(), f1) == pos.end()) {
                location[v] = location[sR] - d;
                stype[v] = 1;
                cLefts.push_back(v);
                used.insert(location[v]);
            } else {
                location[v] = f1;
                stype[v] = 2;
                used.insert(location[v]);
            }
        } else {
            const int d = dist(0, v);
            std::vector<int> pos;
            for (const int p : dRights) {
                const int posA = location[p];
                const int posB = posA - (d - dist(0, p));
                if (posB > location[0] and used.find(posB) == used.end()) {
                    pos.push_back(posB);
                }
            }
            
            const int b = dRights.back();
            const int f1 = location[b] - dist(b, v);
            if (std::find(pos.begin(), pos.end(), f1) == pos.end()) {
                location[v] = location[0] + d;
                stype[v] = 2;
                dRights.push_back(v);
                used.insert(location[v]);
            } else {
                location[v] = f1;
                stype[v] = 1;
                used.insert(location[v]);
            }
        }
    }
    /*
    for (int i = 0; i < N; ++i) {
        std::cout << stype[i] << ' ' << location[i] << std::endl;
    }
    */
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 98628 KB Output is correct
2 Correct 161 ms 98736 KB Output is correct
3 Correct 198 ms 98632 KB Output is correct
4 Correct 209 ms 98744 KB Output is correct
5 Correct 297 ms 98660 KB Output is correct
6 Correct 223 ms 98744 KB Output is correct
7 Correct 235 ms 98740 KB Output is correct
8 Correct 195 ms 98740 KB Output is correct
9 Correct 168 ms 98696 KB Output is correct
10 Correct 188 ms 98768 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 98732 KB Output is correct
2 Correct 175 ms 98632 KB Output is correct
3 Correct 173 ms 98636 KB Output is correct
4 Correct 178 ms 98720 KB Output is correct
5 Correct 213 ms 98632 KB Output is correct
6 Correct 234 ms 98628 KB Output is correct
7 Correct 180 ms 98896 KB Output is correct
8 Correct 185 ms 98780 KB Output is correct
9 Correct 193 ms 98780 KB Output is correct
10 Correct 188 ms 98780 KB Output is correct
11 Correct 227 ms 98684 KB Output is correct
12 Correct 220 ms 98816 KB Output is correct
13 Correct 189 ms 98768 KB Output is correct
14 Correct 258 ms 98744 KB Output is correct
15 Correct 198 ms 98740 KB Output is correct
16 Correct 190 ms 98772 KB Output is correct
17 Correct 217 ms 98796 KB Output is correct
18 Correct 203 ms 98768 KB Output is correct
19 Correct 219 ms 98724 KB Output is correct
20 Correct 215 ms 98672 KB Output is correct