Submission #493604

#	Time	Username	Problem	Language	Result	Execution time	Memory
493604		proton	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

long long merge(int a[], int beg, int mid, int end)
{
    int i = beg, j = mid;
    long long inv = 0;
    while(i < mid and j < end)
        if(a[i] < a[j]) i++;
        else    inv += mid - i, j++;
    std::inplace_merge(a + beg, a + mid, a + end);
    return inv;
}

// sort arr[beg:end) and return no. of inversions
long long inversions(int a[], int beg, int end)
{
    long long inv = 0;
    if(end - beg < 2)   return 0;
    if(end - beg == 2)
    {
        if(a[beg] < a[beg + 1]) return 0;
        else    return swap(a[beg], a[beg + 1]), 1;
    }
    int mid = (beg + end) >> 1;
    inv += inversions(a, beg, mid);
    inv += inversions(a, mid, end);
    inv += merge(a, beg, mid, end);
    return inv;
}

long long count_swaps(vector<int> a) {
    int n = (int) a.size();
    int p[n], idx[n / 2 + 1];
    for(int i = 0, c = 0; i < n; i++)
    {
        if(a[i] < 0)
        {
            p[i] = c;
            idx[-a[i]].push(c + 1);
            c += 2;
        }
    }
    for(int i = 0; i < n; i++) {
        if(a[i] > 0)
        {
            p[i] = idx[a[i]].front();
            idx[a[i]].pop();
        }
    }
    
    return inversions(p, 0, n);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:41:24: error: request for member 'push' in 'idx[(- a.std::vector<int>::operator[](((std::vector<int>::size_type)i)))]', which is of non-class type 'int'
   41 |             idx[-a[i]].push(c + 1);
      |                        ^~~~
shoes.cpp:48:30: error: request for member 'front' in 'idx[a.std::vector<int>::operator[](((std::vector<int>::size_type)i))]', which is of non-class type 'int'
   48 |             p[i] = idx[a[i]].front();
      |                              ^~~~~
shoes.cpp:49:23: error: request for member 'pop' in 'idx[a.std::vector<int>::operator[](((std::vector<int>::size_type)i))]', which is of non-class type 'int'
   49 |             idx[a[i]].pop();
      |                       ^~~