Submission #1212472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212472		simona1230	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1094 ms	18624 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> l[200001],r[200001];
long long count_swaps(std::vector<int> s)
{
    for(int i=0;i<s.size();i++)
    {
        if(s[i]<0)l[-s[i]].push_back(i);
        else r[s[i]].push_back(i);
    }

    long long ans=0;
    vector<pair<int,int> > v;
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<l[i].size();j++)
        {
            if(l[i][j]>r[i][j])ans++;
            v.push_back({min(l[i][j],r[i][j]),max(l[i][j],r[i][j])});
        }
    }
    //cout<<ans<<endl;

    for(int i=0;i<v.size();i++)
    {
        //cout<<v[i].first<<" "<<v[i].second<<endl;
        for(int j=i+1;j<v.size();j++)
        {
            if(v[i].first<v[j].first&&v[j].second<v[i].second)ans+=2;
            if(v[i].first<v[j].first&&v[j].first<v[i].second&&v[i].second<v[j].second)ans++;

            swap(v[i],v[j]);
            if(v[i].first<v[j].first&&v[j].second<v[i].second)ans+=2;
            if(v[i].first<v[j].first&&v[j].first<v[i].second&&v[i].second<v[j].second)ans++;
            swap(v[i],v[j]);
        }
    }
    return ans;
}

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