Submission #1227341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227341		hengliao	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	39 ms	22088 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{
    const ll mxN=2e5+5;

    struct BIT{
        vll tree;
        ll siz;

        void init(ll sz){
            siz=sz+1;
            tree=vll(siz, 0);
        }

        void update(ll idx, ll val){
            idx++;
            for(;idx<siz;idx+=(idx&(-idx))){
                tree[idx]+=val;
            }
        }

        ll getpre(ll idx){
            idx++;
            ll re=0;
            for(;idx>0;idx-=(idx&(-idx))){
                re+=tree[idx];
            }
            return re;
        }

        ll getsum(ll a, ll b){
            return getpre(b)-getpre(a-1);
        }
    };

    ll n;

    vll v[mxN][2];

    ll a[mxN];
    ll p[mxN];

    BIT bit;

}

long long count_swaps(vector<int> s) {
	n=s.size();
    for(ll i=0;i<n;i++){
        if(s[i]<0){
            v[abs(s[i])][0].pb(i);
        }
        else{
            v[s[i]][1].pb(i);
        }
    }
    for(ll i=1;i<=n/2;i++){
        for(ll j=0;j<(ll) v[i][0].size();j++){
            p[v[i][0][j]]=v[i][1][j];
            p[v[i][1][j]]=v[i][0][j];
        }
    }
    memset(a, -1, sizeof(a));
    ll timer=0;
    for(ll i=0;i<n;i++){
        if(a[i]==-1){
            if(s[i]<0){
                a[i]=timer;
                a[p[i]]=timer+1;
            }
            else{
                a[i]=timer+1;
                a[p[i]]=timer;
            }
            timer+=2;
        }
    }
    bit.init(n);
    ll ans=0;
    for(ll i=0;i<n;i++){
        if(a[i]+1<n) ans+=bit.getsum(a[i]+1, n-1);
        bit.update(a[i], 1);
    }
    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