제출 #417640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417640		usachevd0	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1090 ms	2636 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];

ll count_swaps(vector<int> a) {
    int n = a.size();
    for (auto& x : a) {
        if (x < 0) {
            x *= -2;
        } else {
            x = x * 2 + 1;
        }
    }
    ll ans = 0;
    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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15