Submission #201484

#	Time	Username	Problem	Language	Result	Execution time	Memory
201484		combi1k1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	304 ms	274492 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 v[N];

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

queue<int> lef[N];
queue<int> rig[N];

ll  count_swaps(vector<int> S)  {
    int n = S.size();

    for(int i = 1 ; i <= n ; ++i)   {
        int x = S[i - 1];
        if (x < 0)  lef[-x].push(i);
        if (x > 0)  rig[ x].push(i);
    }
    for(int i = 1 ; i <= n ; ++i)
        upd(i,1);

    ld  ans = 0;

    for(int i = 1 ; i <= n ; ++i)   if(!v[i])   {
        int x = abs(S[i - 1]);
        int L = lef[x].front(); lef[x].pop();
        int R = rig[x].front(); rig[x].pop();

        if (L > R)  {
            ans++;
            swap(L,R);
        }
        ans += get(R);
        ans -= get(L) + 1;

        upd(R,-1);  v[R] = 1;
    }
    return  ans;
}
//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    cout << count_swaps({-1,-2,-3,-4,-5,1,2,3,4,5});
//}

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