Submission #949690

#	Time	Username	Problem	Language	Result	Execution time	Memory
949690		Pikachu	Rail (IOI14_rail)	C++17	30 / 100	48 ms	1144 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());
    int second = first + d[0].first;
    location[d[0].second] = second;
    stype[d[0].second] = 2;
    int l = 0, r = d[0].second;
    set<int> mp[4];
    mp[1].insert(first);
    mp[2].insert(second);
    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) {
                    if ((nloc > first && d0 == nloc - first)
                     || (nloc < first && d0 == 2 * second + nloc - first - 2 * (*it))) {
                        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) {
                    if ((nloc < first && d0 == 2 * second - first - nloc)
                     || (nloc > first && d0 == 2 * (*it) - first - nloc)) {
                        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 / 2;
                auto it = mp[1].lower_bound(location[r]);
                auto lmao = it;
                if (it != mp[1].begin() && *(--it) == tmp) {
                    if (nloc > first && d0 == nloc - first) {
                        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) {
                    if (nloc < first && d0 == 2 * second - first - nloc) {
                        location[id] = nloc;
                        stype[id] = 1;
                        done = true;
                     }
                }
            }
        }
        if (!done) {
            assert(d[i + 1].first == d0);
            swap(d[i], d[i + 1]);
            i--;
        }
        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:81:22: warning: variable 'lmao' set but not used [-Wunused-but-set-variable]
   81 |                 auto lmao = it;
      |                      ^~~~

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