Submission #1045407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045407		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	444 ms	137100 KiB

shoes

#include "shoes.h"
#include<bits/extc++.h>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
queue<int> otherpos[100100];
long long calc(vector<int>v){
    long long ans=0;
    int K=0;
    tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update>st;
    for(auto i:v) {
        st.insert(i);
        ans+=K++-st.order_of_key(i);
    }
    return ans;
}
long long count_swaps(std::vector<int> s) {
    int n=s.size()>>1,CC=0;
    vector<int>sup,sup2;
    sup.resize(2*n);
    sup2.resize(2*n);
    for(int i=0;i<n*2;i++)
        if(s[i]<0) sup[i]=2*CC,
            otherpos[-s[i]].push(2*CC+++1);
    for(int i=0;i<n*2;i++)if(s[i]>0)
        sup[i]=otherpos[s[i]].front(),otherpos[s[i]].pop();
    CC=0;
    for(int i=0;i<n*2;i++)
        if(s[i]>0) sup2[i]=2*CC+1,
            otherpos[s[i]].push(2*CC++);
    for(int i=0;i<n*2;i++)if(s[i]<0)
        sup2[i]=otherpos[-s[i]].front(),otherpos[-s[i]].pop();
    assert(calc(sup)==calc(sup2));
    return min(calc(sup),calc(sup2));
}

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