제출 #551005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551005		beedle	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	538 ms	37580 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;
    map <int,vector<int>> idx;
    map <int,int> loc;
    vector <bool> marked(2*n);
    rep(i,0,2*n-1)
    idx[shoes[i]].pb(i);

    ll arr[2*n];

    rep(i,0,2*n-1)
    if(!marked[i])
    {
        ll a=shoes[i];
        ll b=-shoes[i];
        ll i1=i;
        ll i2=idx[b][loc[b]];
        loc[a]++;
        loc[b]++;
        marked[i1]=marked[i2]=true;
        if(a<0)
        arr[i1]=2*i+1, arr[i2]=2*i+2;
        else
        arr[i1]=2*i+2, arr[i2]=2*i+1;
    }

    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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15