Submission #201481

#	Time	Username	Problem	Language	Result	Execution time	Memory
201481		combi1k1	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	176 ms	139904 KiB

shoes

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

int t[N];

int upd(int p)  {
    for(; p > 0 ; p -= p & -p)
        t[p]++;
    return  1;
}
int get(int p)  {
    int ans = 0;
    for(; p < N ; p += p & -p)
        ans += t[p];
    return  ans;
}

queue<int> pos[N];

ll  count_swaps(vector<int> S)  {
    queue<ii> quL;

    int n = S.size() / 2;

    for(int i = 1 ; i <= n + n ; ++i)   {
        int x = S[i - 1];
        if (x < 0)  quL.push(ii(-x,i));
        if (x > 0)  pos[x].push(i);
    }
    ll  ans = 0;

    for(int i = 1 ; i <= n + n ; ++i)   {
        int s = quL.front().X;
        int p = quL.front().Y;  quL.pop();

        ans += p + get(p) - i++;    upd(p); p = pos[s].front(); pos[s].pop();
        ans += p + get(p) - i;      upd(p);
    }
    return  ans;
}

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