Submission #949650

#	Time	Username	Problem	Language	Result	Execution time	Memory
949650		Pikachu	Rail (IOI14_rail)	C++17	0 / 100	49 ms	648 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

template<typename T>
inline bool mini(T &x, const T &val)
{
    if (x > val) return x = val, true;
    return false;
}

template<typename T>
inline bool maxi(T &x, const T &val)
{
    if (x < val) return x = val, true;
    return false;
}

void findLocation(int n, int first, int location[], int stype[])
{
    for (int i = 0; i < n; i++) location[i] = -1;
    location[0] = first;
    stype[0] = 1;
    vector<pair<int,int> > d;
    for (int i = 1; i < n; i++) {
        d.push_back({getDistance(0, i), i});
    }
    sort(d.begin(), d.end());
    location[d[0].second] = first + d[0].first;
    stype[d[0].second] = 2;
    int l = 0, r = d[0].second;
    set<int> mp[4];
    mp[1].insert(first);
    mp[2].insert(first + d[0].first);
    for (int i = 1; i < n - 1; i++) {
        int d0 = d[i].first;
        int id = d[i].second;
        int dl = getDistance(l, id);
        int dr = getDistance(r, id);
        bool done = false;
        if (!done && location[l] + dl < location[r]) {
            int nloc = location[l] + dl;
            int dak = (dr - (location[r] - nloc));
            if (dak % 2 == 0) {
                int tmp = nloc - dak / 2;
                auto it = mp[1].lower_bound(nloc);
                if (it != mp[1].begin() && *(--it) == tmp) {
                    location[id] = nloc;
                    stype[id] = 2;
                    done = true;
                }
            }
        }
        if (!done && location[r] - dr > location[l]) {
            int nloc = location[r] - dr;
            int dak = (dl - (nloc - location[l]));
            if (dak % 2 == 0) {
                int tmp = nloc + dak / 2;
                auto it = mp[2].upper_bound(nloc);
                if (it != mp[2].end() && *it == tmp) {
                    location[id] = nloc;
                    stype[id] = 1;
                    done = true;
                }
            }
        }
        if (!done && location[l] + dl > location[r]) {
            int nloc = location[l] + dl;
            int dak = dr - (nloc - location[r]);
            if (dak % 2 == 0) {
                int tmp = location[r] - dak;
                auto it = mp[1].lower_bound(location[r]);
                if (it != mp[1].begin() && *(--it) == tmp) {
                    location[id] = nloc;
                    stype[id] = 2;
                    done = true;
                }
            }
        }
        if (!done && location[r] - dr < location[l]) {
            int nloc = location[r] - dr;
            int dak = (dl - (location[l] - nloc));
            if (dak % 2 == 0) {
                int tmp = location[l] +  dak / 2;
                auto it = mp[2].upper_bound(location[l]);
                if (it != mp[2].end() && *it == tmp) {
                    location[id] = nloc;
                    stype[id] = 1;
                    done = true;
                }
            }
        }
        mp[stype[id]].insert(location[id]);
        if (stype[id] == 1) {
            if (location[id] < location[l]) l = id;
        }
        if (stype[id] == 2) {
            if (location[id] > location[r]) r = id;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:37:13: warning: unused variable 'd0' [-Wunused-variable]
   37 |         int d0 = d[i].first;
      |             ^~

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