Submission #1020164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020164		abdelhakim	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	348 KiB

shoes

#include <bits/stdc++.h>
#define mod 1000000007LL
#define inf 1e17
#define ll long long
using namespace std;

void printvec(vector<int> vec)
{
    for (auto &&e : vec)
    {
        cout << e << ' ';
    }
    cout << endl;
}

ll count_swaps(vector<int> s)
{
    ll n = s.size()/2;
    bool sametype = true;
    for (int i = 1; i < n; i++)
    {
        if(abs(s[i])!=abs(s[i-1]))
        {
            sametype = false;
            break;
        }
    }
    if(n == 1) return s[0] > s[1];
    else if(!sametype) return n*(n-1)/2;
    else 
    {
        ll ans = 0;
        for (int i = 0; i < 2*n; i++)
        {
            if(s[i] < 0)
            {
                s[i] = -1;
            }
            else s[i] = 1;
        }
        vector<ll> correct(2*n);
        for (int i = 0; i < 2*n; i++)
        {
            if(i%2 == 0) correct[i] = -1;
            else correct[i] = 1;
        }
        // for (int i = 0; i < 2*n-1; i++)
        // {
        //     if(s[i] != correct[i] && s[i+1] != correct[i+1])
        //     {
        //         swap(s[i], s[i+1]);
        //         ans++;
        //     }
        // }
        vector<set<ll>> indices(2);
        vector<ll> subsegs;
        for (int i = 0; i < 2*n; i++)
        {
            if(i == 0 || s[i]!=s[i-1]) subsegs.push_back(i);
            if(s[i]!=correct[i])
            {
                if(s[i] == -1)
                {
                    indices[0].insert(i);
                }
                else indices[1].insert(i);
            }
        }
        for (int i = 0; i < 2*n; i++)
        {
            if(s[i]!=correct[i])
            {
                if(s[i] == -1)
                {
                    auto it = indices[1].lower_bound(i);
                    ll index = *it;
                    indices[1].erase(it);
                    ans += 2*(index - i)-1;
                    ll ne = index - i + 1;
                    ll nsegs = lower_bound(subsegs.begin(), subsegs.end(), index) - lower_bound(subsegs.begin(), subsegs.end(), i)+1;
                    ans -= (ne - nsegs);
                    swap(s[i], s[index]);
                }
                else
                {
                    auto it = indices[0].lower_bound(i);
                    ll index = *it;
                    indices[0].erase(it);
                    ans += 2*(index - i)-1;
                    ll ne = index - i + 1;
                    ll nsegs = lower_bound(subsegs.begin(), subsegs.end(), index) - lower_bound(subsegs.begin(), subsegs.end(), i)+1;
                    ans -= (ne - nsegs);
                    swap(s[i], s[index]);
                }
            }
        }
        return ans;
    }
}

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