Submission #791274

#	Time	Username	Problem	Language	Result	Execution time	Memory
791274		skittles1412	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1074 ms	15632 KiB

shoes

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

long count_inversions(const vector<int>& arr) {
    int n = sz(arr), ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += arr[i] > arr[j];
        }
    }
    return ans;
}

ll count_swaps(vector<int> arr) {
    int n = sz(arr);

    map<int, vector<pair<int, int>>> mp;
    for (int i = 0; i < n; i++) {
        mp[abs(arr[i])].emplace_back(arr[i], i);
    }

    vector<array<int, 3>> s_pairs;

    long ans = 0;

    for (auto& [k, v] : mp) {
        vector<int> t_pos;
        for (auto& [_x, i] : v) {
            t_pos.push_back(i);
        }

        int neg = 0, pos = 1;
        vector<int> carr;
        int rmap[sz(v)];

        for (int i = 0; i < sz(v); i++) {
            auto& [x, ei] = v[i];
            if (x < 0) {
                rmap[neg] = ei;
                carr.push_back(t_pos[neg]);
                neg += 2;
            } else {
                rmap[pos] = ei;
                carr.push_back(t_pos[pos]);
                pos += 2;
            }
        }
        ans += count_inversions(carr);

        for (int i = 0; i < sz(v); i += 2) {
            s_pairs.push_back({rmap[i], rmap[i + 1], k});
        }
    }

    for (auto& [ql, qr, _ty] : s_pairs) {
        if (ql > qr) {
            swap(ql, qr);
        }
    }

    for (auto& [l1, r1, t1] : s_pairs) {
        for (auto& [l2, r2, t2] : s_pairs) {
            if (t1 == t2) {
                continue;
            }
            if (l1 <= l2 && r2 <= r1) {
                ans += 2;
            } else if (l1 <= l2 && l2 <= r1 && r1 <= r2) {
                ans++;
            }
        }
    }

    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15