Submission #540534

#	Time	Username	Problem	Language	Result	Execution time	Memory
540534		__Variatto	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	8 ms	9940 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const ll MAX=2e5+10, S=1<<19;
ll n, curr, licz[MAX], x[MAX];
vector<ll>vec[MAX];
ll t[2*S+10];
void Insert(ll v){
    v+=S;
    while(v){
        t[v]++;
        v/=2;
    }
}
ll Query(ll a, ll b){
    ll w=0;
    a+=S-1, b+=S+1;
    while(a+1<b){
        if(a%2==0) w+=t[a+1];
        if(b%2==1) w+=t[b-1];
        a/=2, b/=2;
    }
    return w;
}
ll a[MAX];
ll count_swaps(vector<int>xx){
    n=xx.size()/2;
    for(ll i=1; i<=2*n; i++){
        curr=xx[i-1];
        if(curr>0) vec[curr].pb(i);
        a[i]=curr;
    }
    ll akt=0;
    for(ll i=1; i<=2*n; i++){
        curr=a[i];
        if(curr<0)
            x[i]=akt*2, x[vec[-curr][licz[-curr]++]]=akt*2+1;
        else
            x[i]=akt*2+1, x[vec[-curr][licz[-curr]++]]=akt*2;
        akt++;
    }
    ll wyn=0;
    for(ll i=1; i<=2*n; i++){
        wyn+=Query(x[i]+1, S-1);
        Insert(x[i]);
    }
    return wyn;
}
/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
}*/

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