Submission #551000

#	Time	Username	Problem	Language	Result	Execution time	Memory
551000		beedle	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	55 ms	14800 KiB

shoes

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

ll _mergeSort(ll arr[], ll temp[],  
               ll left, ll right); 
ll merge(ll arr[], ll temp[],  
          ll left, ll mid, ll right); 
  
/* This function sorts the input  
   array and returns the number  
   of inversions in the array */
ll mergeSort(ll arr[], ll array_size) 
{ 
    ll temp[array_size]; 
    return _mergeSort(arr, temp, 0,  
                      array_size - 1); 
} 
  
/* An auxiliary recursive function that  
   sorts the input array and returns the  
   number of inversions in the array. */
ll _mergeSort(ll arr[], ll temp[],  
               ll left, ll right) 
{ 
    ll mid, inv_count = 0; 
    if (right > left)  
    { 
        /* Divide the array llo two parts and  
           call _mergeSortAndCountInv() for  
           each of the parts */
        mid = (right + left) / 2; 
  
        /* Inversion count will be sum of inversions  
           in left-part, right-part and number of  
           inversions in merging */
        inv_count += _mergeSort(arr, temp,  
                                left, mid); 
        inv_count += _mergeSort(arr, temp,  
                                mid + 1, right); 
  
        // Merge the two parts 
        inv_count += merge(arr, temp,  
                           left, mid + 1, right); 
    } 
    return inv_count; 
} 
  
/* This funt merges two sorted arrays and  
   returns inversion count in the arrays.*/
ll merge(ll arr[], ll temp[],  
          ll left, ll mid, ll right) 
{ 
    ll i, j, k; 
    ll inv_count = 0; 
  
    // i is index for left subarray 
    i = left; 
  
    // j is index for right subarray  
    j = mid;  
  
    // k is index for resultant merged  
    // subarray 
    k = left;  
  
    while ((i <= mid - 1) &&  
           (j <= right))  
    { 
        if (arr[i] <= arr[j])  
        { 
            temp[k++] = arr[i++]; 
        } 
        else 
        { 
            temp[k++] = arr[j++]; 
  
            /* This is tricky -- see above  
               explanation/diagram for merge()*/
            inv_count = inv_count + (mid - i); 
        } 
    } 
  
    /* Copy the remaining elements of left  
       subarray (if there are any) to temp*/
    while (i <= mid - 1) 
        temp[k++] = arr[i++]; 
  
    /* Copy the remaining elements of right  
       subarray (if there are any) to temp*/
    while (j <= right) 
        temp[k++] = arr[j++]; 
  
    /* Copy back the merged elements to  
       original array*/
    for (i = left; i <= right; i++) 
        arr[i] = temp[i]; 
  
    return inv_count; 
} 

ll count_swaps(vector <int> shoes)
{
    ll n=sz(shoes)/2;
    vector <ll> v;
    vector <vector<ll>> idx(n+1, vector <ll> ());
    vector <ll> s(2*n);
    rep(i,0,2*n-1)
    if(shoes[i]<0)
    {
        ll val=-shoes[i];
        v.pb(val);
        idx[val].pb(sz(v)-1);
        s[i]=2*sz(v)-1;
    }
    vector <ll> last(n+1,0);
    rep(i,0,2*n-1)
    if(shoes[i]>0)
    {
        ll occ=last[shoes[i]];
        last[shoes[i]]++;
        s[i]=2*idx[shoes[i]][occ]+2;
    }

    ll arr[2*n];
    rep(i,0,2*n-1)
    arr[i]=s[i];

    return mergeSort(arr,2*n);
}

// signed main()
// {
//     fast;

    // freopen("milkorder.in","r",stdin);
    // freopen("milkorder.out","w",stdout);

//     cout<<count_swaps({-2 ,3 ,-4 ,-3 ,-2 ,2 ,4 ,2});

//     return 0;
// }

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