Submission #1003168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003168		Sharky	Rail (IOI14_rail)	C++17	100 / 100	93 ms	98900 KiB

rail

// amogus orz

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

const int N = 5001;
int cache[N][N];

int dist(int i, int j) {
    if (i == j) return 0;
    if (cache[i][j] != -1) return cache[i][j];
    return cache[i][j] = cache[j][i] = getDistance(i, j);
}

void findLocation(int n, int first, int pos[], int stype[]) {
    map<int, char> sus;
    vector<char> t(n, '?');
    t[0] = 'C';
    pos[0] = first;
    sus[first] = 'C';
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cache[i][j] = -1;
    int mn = inf, id = 0;
    for (int i = 1; i < n; i++) if (dist(0, i) < mn) mn = dist(0, i), id = i;
    t[id] = 'D';
    pos[id] = first + dist(0, id);
    sus[pos[id]] = 'D';
    vector<pair<int, int>> l, r;
    for (int i = 1; i < n; i++) {
        if (i == id) continue;
        if (dist(0, id) + dist(id, i) == dist(0, i) && dist(0, id) > dist(id, i)) {
            t[i] = 'C';
            pos[i] = first + dist(0, id) - dist(id, i);
            sus[pos[i]] = 'C';
            continue;
        }
        if (dist(0, id) + dist(id, i) == dist(0, i)) l.push_back({dist(id, i), i});
        else r.push_back({dist(0, i), i});
    }
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());
    // for (int i = 0; i < r.size(); i++) cout << r[i].first << ' ' << r[i].second << '\n';
    int leftmost = 0, rightmost = id;
    for (int i = 0; i < l.size(); i++) {
        int cur = l[i].second;
        // cout << "left " << cur << '\n';
        int magic = pos[leftmost] + ((dist(cur, leftmost) + dist(leftmost, id) - dist(id, cur)) / 2);
        // assert(sus.count(magic));
        if (sus[magic] == 'C') {
            t[cur] = 'D';
            pos[cur] = dist(cur, leftmost) + pos[leftmost];
            sus[pos[cur]] = 'D';
        } else {
            t[cur] = 'C';
            pos[cur] = pos[id] - dist(id, cur);
            sus[pos[cur]] = 'C';
            leftmost = cur;
        }
    }
    for (int i = 0; i < r.size(); i++) {
        int cur = r[i].second;
        // cout << "right " << cur << '\n';
        int magic = pos[rightmost] - ((dist(cur, rightmost) + dist(rightmost, 0) - dist(cur, 0)) / 2);
        // cout << magic << '\n';
        // assert(sus.count(magic));
        if (sus[magic] == 'D') {
            t[cur] = 'C';
            pos[cur] = pos[rightmost] - dist(rightmost, cur);
            sus[pos[cur]] = 'C';
        } else {
            t[cur] = 'D';
            pos[cur] = pos[0] + dist(0, cur);
            sus[pos[cur]] = 'D';
            rightmost = cur;
        }
    }
    for (int i = 0; i < n; i++) {
        stype[i] = (t[i] == 'C' ? 1 : 2);
        // cout << stype[i] << ' ' << pos[i] << '\n';
    }
}

/*
4
6
1 779
1 0
2 10000
1 9226
2 9768
2 5543
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
rail.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~

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