Submission #1006588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006588		onbert	Rail (IOI14_rail)	C++17	100 / 100	104 ms	98636 KiB

rail

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

void findLocation(int n, int pos0, int pos[], int type[]) {
    pos[0] = pos0, type[0] = 1;
    if (n==1) return;
    int dist[n][n];
    vector<pair<int,int>> v;
    for (int i=1;i<n;i++) {
        dist[0][i] = getDistance(0, i);
        v.push_back({dist[0][i], i});
    }
    sort(v.begin(), v.end());
    vector<pair<int,int>> Df, Cb;
    int pos1, s1;
    for (auto [d, id]:v) {
        if (Df.size() == 0) {
            pos1 = pos[id] = pos0 + dist[0][id], type[id] = 2;
            s1 = id;
            Df = {{pos[id], id}};
            continue;
        }
        int last = Df.back().second;
        dist[last][id] = getDistance(last, id);
        int curpos = pos[last] - dist[last][id];
        int nxt = (*lower_bound(Df.begin(), Df.end(), make_pair(curpos, 0))).second;
        if (dist[last][id] - (pos[last]-pos[nxt]) + dist[0][nxt] == dist[0][id]) {
            if (curpos < pos0) {
                dist[s1][id] = dist[0][id] - dist[0][s1];
                if (Cb.size() == 0) {
                    pos[id] = pos1 - dist[s1][id], type[id] = 1;
                    Cb = {{-pos[id], id}};
                    continue;
                }
                int last1 = Cb.back().second;
                // cout << Cb[0].first << " " << Cb[0].second << endl;
                // cout << id << " " << last1 << endl;
                dist[last1][id] = getDistance(last1, id);
                int curpos1 = -pos[last1] - dist[last1][id];
                int nxt1 = (*lower_bound(Cb.begin(), Cb.end(), make_pair(curpos1, 0))).second;
                // cout << id << " " << curpos1 << " " << nxt1 << endl;
                // cout << dist[last1][id] << " " << pos[nxt1]-pos[last1] << " " << dist[s1][nxt1] << endl;
                if (dist[last1][id] - (pos[nxt1]-pos[last1]) + dist[s1][nxt1] == dist[s1][id]) {
                    pos[id] = -curpos1, type[id] = 2;
                } else {
                    pos[id] = pos1 - dist[s1][id], type[id] = 1;
                    Cb.push_back({-pos[id], id});
                }
            } else pos[id] = curpos, type[id] = 1;
        } else {
            pos[id] = pos0 + dist[0][id], type[id] = 2;
            Df.push_back({pos[id], id});
        }
    }
    // for (int i=0;i<n;i++) cout << type[i] << " " << pos[i] << endl;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:32:36: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |                     pos[id] = pos1 - dist[s1][id], type[id] = 1;
      |                               ~~~~~^~~~~~~~~~~~~~
rail.cpp:44:93: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |                 if (dist[last1][id] - (pos[nxt1]-pos[last1]) + dist[s1][nxt1] == dist[s1][id]) {
      |                                                                                  ~~~~~~~~~~~^

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