Submission #417641

#	Time	Username	Problem	Language	Result	Execution time	Memory
417641		usachevd0	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	194 ms	21108 KiB

shoes

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "shoes.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int maxN = 2e5 + 5;
const ll INF64 = 1e18;

int mn[maxN];
vector<int> pos[maxN];

namespace fnw {
    int f[maxN];
    
    void add(int i, int delta) {
        for (++i; i < maxN; i += i & -i)
            f[i] += delta;
    }
    int pref(int i) {
        int ans = 0;
        for (++i; i >= 1; i -= i & -i)
            ans += f[i];
        return ans;
    }
}

ll count_swaps(vector<int> a) {
    int n = a.size();
    for (auto& x : a) {
        if (x < 0) {
            x *= -2;
        } else {
            x = x * 2 + 1;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        pos[a[i]].push_back(i);
    }
    ll ans = 0;
    set<pli> q;
    for (int x = 1; x <= n / 2; ++x)
        if (!pos[2 * x].empty()) {
            ll f = pos[2 * x].back() + pos[2 * x + 1].back() + (int)(pos[2 * x].back() > pos[2 * x + 1].back());
            q.insert({f, x});
        }
    for (int i = 0; i < n; ++i)
        fnw::add(i, 1);
    while (!q.empty()) {
        int x = q.begin()->se;
        q.erase(q.begin());
        
        int i = pos[2 * x].back();
        pos[2 * x].pop_back();
        int j = pos[2 * x + 1].back();
        pos[2 * x + 1].pop_back();
        
        ans += fnw::pref(i) + fnw::pref(j) - 3 + (int)(i > j);
        fnw::add(i, -1);
        fnw::add(j, -1);
        
        if (!pos[2 * x].empty()) {
            ll f = pos[2 * x].back() + pos[2 * x + 1].back() + (int)(pos[2 * x].back() > pos[2 * x + 1].back());
            q.insert({f, x});
        }
    }
    // for (int i = 0; i < n; i += 2) {
    //     fill(mn, mn + n + 2, -1);
    //     for (int j = 0; j < n; ++j) {
    //         if (a[j] != 0 && mn[a[j]] == -1)
    //             mn[a[j]] = j;
    //     }
    //     ll minF = INF64;
    //     int minX = -1;
    //     for (int x = 1; x <= n / 2; ++x)
    //         if (mn[2 * x] != -1) {
    //             ll f = mn[2 * x] + mn[2 * x + 1];
    //             if (mn[2 * x] > mn[2 * x + 1])
    //                 ++f;
    //             if (chkmin(minF, f))
    //                 minX = x;
    //         }
    //     // ans += minF;
    //     auto f = [&](int j) -> ll {
    //         int res = 0;
    //         while (j > 0) {
    //             res += (a[--j] != 0);
    //         }
    //         return res;
    //     };
    //     int j1 = f(mn[2 * minX]), j2 = f(mn[2 * minX + 1]);
    //     ans += j1 + j2 - 1;
    //     if (j1 > j2) {
    //         swap(j1, j2);
    //         ++ans;
    //     }
    //     a[mn[2 * minX]] = a[mn[2 * minX + 1]] = 0;
    //     // rotate(a.begin() + i, a.begin() + j1, a.begin() + j1 + 1);
    //     // rotate(a.begin() + i + 1, a.begin() + j2, a.begin() + j2 + 1);
    // }
    return ans;
}


#ifdef LOCAL
int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
        int n;
    assert(1 == scanf("%d", &n));
    vector<int> S(2 * n);
    for (int i = 0; i < 2 * n; i++)
        assert(1 == scanf("%d", &S[i]));
    fclose(stdin);

    long long result = count_swaps(S);

    printf("%lld\n", result);
    fclose(stdout);
    
    return 0;
}
#endif

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