Submission #438734

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

shoes

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define ll long long

using namespace std;

class BIT
{
private:
vector<ll> tree;
int n;
public:

BIT(int sizeOfTree)
{
    n = sizeOfTree;
    tree.resize(n + 1, 0);
}

void update(int index, ll value)
{
    index++;
    while (index < n)
        tree[index] += value, index += index & (-index);
}

ll query(int index)
{
    index++;
    ll out = 0;
    while (index > 0)
        out += tree[index], index -= index & (-index);
    return out;
}

};

map<int, vector<int> > located;
map<int, int> used;
map<int, bool> matched;

ll count_swaps(vector<int> S)
{
    int n = S.size();
    BIT passed(n);

    for (int i = 0; i < n; i++)
        located[S[i]].push_back(i);

    ll out = 0;
    for (int i = 0; i < n; i++)
    {
        if (matched[i])
            continue;
        int counterpart = upper_bound(located[-S[i]].begin(), located[-S[i]].end(), used[-S[i]]) - located[-S[i]].begin();
        int val = located[-S[i]][counterpart];
        matched[val] = true;
        int swaps = (val - i) /*+ passed.query(val)*/;
        passed.update(val, 1);
        used[-S[i]] = val;
        used[S[i]] = i;

        if (S[i] < 0)
            swaps--;
        out += swaps;
    }
    return out;
}

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cout << count_swaps(arr) << endl;
    return 0;
}

Compilation message (stderr)

shoes.cpp: In function 'int main()':
shoes.cpp:79:25: error: could not convert '(int*)(& arr)' from 'int*' to 'std::vector<int>'
   79 |     cout << count_swaps(arr) << endl;
      |                         ^~~
      |                         |
      |                         int*