Submission #1064005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064005		jerzyk	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	62 ms	24148 KiB

shoes

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int drz[2 * N];
vector<int> pos[N][2];
int tab[N];
bool vis[N];

inline int A(int x)
{
    if(x < 0) return -x;
    return x;
}

void Add(int v)
{
    v += N;
    while(v > 0)
        {++drz[v]; v /= 2;}
}

int Query(int a, int b)
{
    a += N - 1; b += N + 1;
    int s = 0;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) s += drz[a + 1];
        if(b % 2 == 1) s += drz[b - 1];
        a /= 2; b /= 2;
    }
    return s;
}

long long count_swaps(vector<int> s)
{
    int n = s.size();
    ll ans = 0LL;
    for(int i = 0; i < n; ++i)
    {
        tab[i + 1] = s[i];
        pos[A(s[i])][(s[i] < 0)].pb(i + 1);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < 2; ++j)
            reverse(pos[i][j].begin(), pos[i][j].end());
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i]) continue;
        int r = (tab[i] < 0), x = A(tab[i]);
        int j =  pos[x][r ^ 1].back();
        //cerr << "swp i: " << i << " " << tab[i] << " j: " << j << " " << ans << "\n";
        pos[x][0].pop_back(); pos[x][1].pop_back();
        ans += (ll)(j - i - 1);
        ans += (ll)Query(j, n) - (ll)Query(i, n);
        Add(j);
        vis[j] = true;
        if(r == 0) ++ans;
    }
    return ans;
}

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