Submission #1246148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246148		qwusha	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	15 ms	1964 KiB

shoes

#include "shoes.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second
typedef long long ll;
using namespace std;

int inf = 1e9 + 7;


bool check(vector<int> &vec) {
    int n = vec.size() / 2;
    for (int i = 0; i < 2 * n; i+=2) {
        if (abs(vec[i]) != abs(vec[i + 1]))
            return 0;
        if (vec[i] > 0 || vec[i + 1] < 0)
            return 0;
    }
    return 1;
}


long long count_swaps(vector<int> s) {
    ll n = s.size() / 2;
    bool same = 1;
    for (int i = 0; i < s.size(); i++) {
        if (abs(s[i]) != abs(s[0]))
            same = 0;
    }
    if (n <= 1000) {
        ll res = 0;
        for (int i = 0; i < 2 * n; i+=2) {
            map<int, pair<int, int>> pos, neg;
            for (int j = i ; j < 2 * n; j++) {
                if (s[j] < 0) {
                    if (neg.find(abs(s[j])) == neg.end()) {
                        neg[abs(s[j])] = {j - i, j};
                    }
                } else {
                    if (pos.find(s[j]) == pos.end()) {
                        if (neg.find(abs(s[j])) == neg.end()) {
                            pos[abs(s[j])] = {j - i, j};
                        } else {
                            pos[abs(s[j])] = {j - i - 1, j};
                        }
                    }
                }
            }
            map<int, int> sum;
            for (auto [va, pa] : pos) {
                sum[va] += pa.fi  + neg[va].fi;
            }
            int mini = 1e9;
            pair<int, int> ind;
            int bval = -1;
            for (auto [va, su] : sum) {
                if (su < mini) {
                    bval =va;
                    mini = su;
                    ind = {pos[va].se, neg[va].se};
                }
            }
            res += (ll)mini;
            if (min(ind.fi, ind.se) == i + 1) {
                swap(s[i], s[i + 1]);
            }
            for (int j = max(ind.fi, ind.se); j>= i + 2; j--) {
                if (j <= min(ind.fi, ind.se)) {
                    s[j] = s[j - 2];
                } else {
                    s[j] = s[j - 1];
                }
            }
            s[i] = -bval;
            s[i + 1] = bval;
        }
        return res;
    } else if (same) {
        ll sum = 0;
        int cr = 0;
        int supr = 0;
        int cl = 0;
        int supl = 1;
        int type = 0;
        for (int i = 0; i < 2 * n; i++) {
            if (type == 0) {
                if (s[i] > 0) {
                    cr++;
                    supl++;
                } else {
                    sum += cr - supr;
                    supr++;
                    cl++;
                    if (supr > cr) {
                        type = 1;
                    }
                }
            } else {
                if (s[i] > 0) {
                    sum += cl - supl;
                    cr++;
                    supl++;
                    if (supl > cl) {
                        type = 0;
                    }
                } else {
                    supr++;
                    cl++;
                }
            }
        }
        return sum;
    } else {
        ll res = n * (n - 1) / 2;
        return res;
    }
}

/*
signed main() {
    int n;
    cin >> n;
    vector<int> s(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> s[i];
    }
    int res = count_swaps(s);
    cout << res << endl;
}
*/

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