Submission #1020104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020104		abdelhakim	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1083 ms	3268 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;
    ll ans = 0;
    for (int i = 0; i < 2*n; i++)
    {
        if((s[0] > 0) || (i!=0 && s[i] > 0 && s[i-1] != -s[i]))
        {
            for (int j = i+1; j < 2*n; j++)
            {
                swap(s[j],s[j-1]);
                ans++;
                if(s[j] == s[j-1]) ans--;
                if(s[j] == -s[j-1]) {i--; break;}
            }
        }
        else if(s[i] < 0 && s[i+1] != -s[i])
        {
            for (int j = i+1; j < 2*n-1; j++)
            {
                swap(s[j],s[j-1]);
                ans++;
                if(s[j] == s[j-1])ans--;
                if(s[j] == -s[j+1] && s[j]!=s[j-1]) {i--; break;}
            }
        }
    }
    return ans;
    // 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);
    //     for (int i = 0; i < 2*n; 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;
    //                 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;
    //                 swap(s[i], s[index]);
    //             }
    //         }
    //     }
    //     return ans;
    // }
}
// int main()
// {
//     cout << count_swaps({-1, 1, -1, -1, -1, 1, 1
// , 1}) << 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