Submission #540539

#	Time	Username	Problem	Language	Result	Execution time	Memory
540539		__Variatto	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	102 ms	26856 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], licz2[MAX];
bool odw[MAX];
vector<ll>wie[MAX], mnie[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) wie[curr].pb(i);
        else mnie[-curr].pb(i);
        a[i]=curr;
    }
    ll akt=0;
    for(ll i=1; i<=2*n; i++){
        curr=a[i];
        if(odw[i]) continue;
        if(curr<0){
            x[i]=akt*2, x[wie[-curr][licz[-curr]]]=akt*2+1, odw[wie[-curr][licz[-curr]]]=true;
            licz[-curr]++, licz2[-curr]++;
        }
        else{
            x[i]=akt*2+1, x[mnie[curr][licz2[curr]]]=akt*2, odw[mnie[curr][licz2[curr]]]=true;
            licz[curr]++, licz2[curr]++;
        }
        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);
    int nn;
    cin>>nn;
    vector<int>xd;
    for(int i=1; i<=nn; i++){
        int curr;
        cin>>curr;
        xd.pb(curr);
    }
    cout<<count_swaps(xd)<<"\n";

}*/

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