Submission #1255231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255231		nerrrmin	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	76 ms	22964 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
long long a[maxn], n;
long long merge_sort(long long l, long long r)
{
    if(l == r)return 0;
    long long mid = (l + r)/2;
    long long onleft = merge_sort(l, mid);
    long long onright = merge_sort(mid+1, r);
    long long ans = onleft + onright;
     long long i = l, j = mid+1;
     vector < long long > w;
     while(i <= mid && j <= r)
     {
         if(a[i] < a[j])
         {
             w.pb(a[i]);
             i ++;
         }
         else
         {
             w.pb(a[j]);
             j ++;
             ans += (mid - i + 1);
         }
     }
     while(i <= mid)
     {
         w.pb(a[i]);
         i ++;
     }
     while(j <= r)
     {
         w.pb(a[j]);
         j ++;
     }
     long long p = 0;
     for (long long i = l; i <= r; ++ i)
     {
         a[i] = w[p];
         p ++;
     }
     return ans;
}
vector < int > lt[maxn], rt[maxn];
bool cmp(pair < int, int > p1, pair < int, int > p2)
{
    int min1 = min(p1.first, p1.second);
    int min2 = min(p2.first, p2.second);
    return (min1 < min2);
}
long long count_swaps(std::vector< int > s)
{


    long long i = 1;
    for (auto x: s)
    {
        if(x < 0)lt[abs(x)].pb(i);
        else rt[abs(x)].pb(i);
        i ++;
    }
    n = s.size();
    long long pos = 0;
    vector < pair < int, int > > g;
    for (long long i = 1; i <=n ; ++ i)
    {
        int sz = lt[i].size();
        for (int j = 0; j < sz; ++ j)
        {
            long long f = lt[i][j];
            long long s = rt[i][j];
            g.pb(make_pair(f, s));
        }
    }
    sort(g.begin(), g.end(), cmp);
    for (auto &[pos1, pos2]: g)
    {
        a[pos1] = pos;
        pos ++;
        a[pos2] = pos;
        pos ++;
    }
    return merge_sort(1, n);
}

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