Submission #724297

#	Time	Username	Problem	Language	Result	Execution time	Memory
724297		PixelCat	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	75 ms	22076 KiB

shoes

#include "shoes.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200010;

#define LO(x) (x & (-x))
struct BIT {
    int n;
    int a[MAXN];
    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
    }
    int ask(int i) {
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
} bit;

vector<int> l[MAXN];
vector<int> r[MAXN];

int solve1(vector<int32_t> s) {
    int n = sz(s) / 2;
    For(i, 1, n) {
        l[i].clear();
        r[i].clear();
    }
    For(i, 0, n * 2 - 1) {
        if(s[i] < 0) l[-s[i]].eb(i + 1);
        else r[s[i]].eb(i + 1);
    }
    vector<pii> owo;
    int add = 0;
    For(siz, 1, n) {
        For(i, 0, sz(l[siz]) - 1) {
            int a = l[siz][i];
            int b = r[siz][i];
            owo.eb(a, b);
        }
    }
    sort(all(owo), [&](pii a, pii b) {
        return a.F + a.S < b.F + b.S;
    });
    int res = 0;
    bit.init(n * 2);
    For(i, 1, n * 2) bit.add(i, 1);
    for(auto &p:owo) {
        bit.add(p.F, -1);
        res += bit.ask(p.F);
        bit.add(p.S, -1);
        res += bit.ask(p.S);
    }
    return res + add;
}

// int solve1(vector<int32_t> s) {
//     int n = sz(s) / 2;
//     For(i, 1, n) {
//         l[i].clear();
//         r[i].clear();
//     }
//     For(i, 0, n * 2 - 1) {
//         if(s[i] < 0) l[-s[i]].eb(i + 1);
//         else r[s[i]].eb(i + 1);
//     }
//     vector<pii> owo;
//     For(siz, 1, n) {
//         For(i, 0, sz(l[siz]) - 1) {
//             int a = l[siz][i];
//             int b = r[siz][i];
//             owo.eb(a, b);
//         }
//     }
//     sort(all(owo), [&](pii a, pii b) {
//         if(a.F < b.F && a.S < b.S) return true;
//         return false;
//     });
//     int res = 0;
//     bit.init(n * 2);
//     For(i, 1, n * 2) bit.add(i, 1);
//     For(_, 1, n) {
//         int mn = 10000000, idx = -1;
//         For(i, 0, sz(owo) - 1) {
//             auto &p = owo[i];
//             int cost = bit.ask(p.F) + bit.ask(p.S) - 2 - (p.F < p.S);
//             if(cost < mn) {
//                 mn = cost;
//                 idx = i;
//             }
//         }
//         auto &p = owo[idx];
//         res += mn;
//         bit.add(p.F, -1);
//         bit.add(p.S, -1);
//         swap(owo[idx], owo[sz(owo) - 1]);
//         owo.pop_back();
//     }
//     return res;
// }

long long count_swaps(std::vector<int32_t> s) {
    return solve1(s);
}

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