Submission #1217101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217101		Joon_Yorigami	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1096 ms	12724 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

const int MAX_N = 200001;

ll count_swaps(vector<int> owo)
{
    ll n = owo.size();
    vll arr;
    for(auto num:owo)
        arr.push_back(num);
    vll cnt(MAX_N,-1);
    vector<vll> val(MAX_N,vll());
    ll curr=2;
    for(int i=0;i<n;i++)
    {
        if(arr[i]<0)
            continue;
        val[arr[i]].push_back(curr);
        arr[i]=curr;
        curr+=2;
    }
    for(int i=0;i<n;i++)
    {
        if(arr[i]>0)
            continue;
        cnt[abs(arr[i])]+=1;
        arr[i]=val[abs(arr[i])][cnt[abs(arr[i])]]-1;
    }
    ll ans = 0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            ans += arr[i] > arr[j];
    return ans;
}
/*
int main()
{
    cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
}
*/

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