Submission #483622

#	Time	Username	Problem	Language	Result	Execution time	Memory
483622		Lam_lai_cuoc_doi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	66 ms	20676 KiB

shoes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr ll mod = 998244353;
struct FenwickTRee
{
    int n;
    int a[N];
    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }
    int Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} f;

int n, a[N], pos[N];
bool Match[N];
vector<int> Left[N], Right[N];

// A... Ảo thật đấy
// One of the optimal ways to swap is to keep the order of shoes by the time it appear

long long count_swaps(vector<int> a)
{
#define IsLeft(x) (a[x] < 0)
    int n = a.size();
    f.n = n;

    for (int i = 0; i < n; ++i)
        if (IsLeft(i))
            Left[-a[i]].emplace_back(i);
        else
            Right[a[i]].emplace_back(i);

    for (int i = 1; i <= n; ++i)
    {
        reverse(Left[i].begin(), Left[i].end());
        reverse(Right[i].begin(), Right[i].end());
    }

    ll ans(0);
    int l(0);

    for (int i = 0; i < n; ++i)
    {
        if (Match[i])
            continue;

        int other;
        if (IsLeft(i))
        {
            other = Right[-a[i]].back();
            pos[i] = ++l;
            pos[other] = ++l;
        }
        else
        {
            other = Left[a[i]].back();
            pos[other] = ++l;
            pos[i] = ++l;
        }

        Match[i] = Match[other] = 1;

        Left[abs(a[i])].pop_back();
        Right[abs(a[i])].pop_back();
    }

    // Count inversions

    for (int i = 0; i < n; ++i)
    {
        ans += f.Get(pos[i], n);
        f.Update(pos[i], 1);
    }

    return ans;
}/*

void Read()
{
    int n;
    cin >> n;
    vector<int> a(n * 2);
    for (int i = 0; i < n * 2; ++i)
        cin >> a[i];
    cout << count_swaps(a) << "\n";
}

void Solve()
{
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("palesta.INP", "r"))
    {
        freopen("paletsa.inp", "r", stdin);
        freopen("palesta.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
11
-1 4
-4 2
-5 0
0 0
-3 -2
1 -2
5 -2
2 -3
-1 -4
1 -4
3 -4
*/

Compilation message (stderr)

shoes.cpp:144:1: warning: "/*" within comment [-Wcomment]
  144 | /*
      |  
shoes.cpp: In function 'void read(T&)':
shoes.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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