Submission #199325

#	Time	Username	Problem	Language	Result	Execution time	Memory
199325		mythos	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

struct Fenwick {
    vector<int> a;
    int n;

    Fenwick(int n): n(n), a(vector<int>(n, 0)) {}

    int get(int j) {
        int res = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) res += a[j];
        return res;
    }

    int get(int l, int r) {
        return (count(r) - count(l - 1));
    }

    void set(int id) {
        for (; id < n; id = id | (id + 1)) a[id]++;
    }
};

vector<int> create_ind(int n, vector<int> &s) {
    vector<int> ind(2 * n + 1);
    for (int i = 0; i < 2 * n; i++) ind[s[i] + n] = i;
    return ind;
}

long long count_adj(int n, vector<int> &s) {
    vector<int> id = create_ind(n, s);
    Fenwick fw = Fenwick(2 * n);
    long long ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] != 0) {
            int pos = id[n - s[i]];
            ans += pos - i - fw.get(i, pos) - (s[i] < 0 ? 1 : 0);
            s[pos] = 0;
            fw.set(pos);
        }
    }
    return ans;
}

void change(vector<int> &v) {
    int n = (int) v.size() / 2;
    vector<int> cnt(n, 0);

    for (int i = 0; i < 2 * n; i++) {
        if (v[i] > 0) cnt[v[i] - 1]++;
    }
    for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];

    vector<int> cntl = cnt, cntr = cnt;

    for (int i = 0; i < 2 * n; i++) {
        if (v[i] > 0) v[i] = (--cntr[v[i] - 1]) + 1;
        else v[i] -= - ((--cntl[-v[i] - 1]) + 1);
    }
}

long long count_swaps(vector<int> s) {
    change(s);
    int n = (int) s.size() / 2;
    return count_adj(n, s);
}

Compilation message (stderr)

shoes.cpp: In constructor 'Fenwick::Fenwick(int)':
shoes.cpp:8:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
     int n;
         ^
shoes.cpp:7:17: warning:   'std::vector<int> Fenwick::a' [-Wreorder]
     vector<int> a;
                 ^
shoes.cpp:10:5: warning:   when initialized here [-Wreorder]
     Fenwick(int n): n(n), a(vector<int>(n, 0)) {}
     ^~~~~~~
shoes.cpp: In member function 'int Fenwick::get(int, int)':
shoes.cpp:19:24: error: no matching function for call to 'count(int&)'
         return (count(r) - count(l - 1));
                        ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from shoes.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:4076:5: note: candidate: template<class _IIter, class _Tp> typename std::iterator_traits<_Iterator>::difference_type std::count(_IIter, _IIter, const _Tp&)
     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
     ^~~~~
/usr/include/c++/7/bits/stl_algo.h:4076:5: note:   template argument deduction/substitution failed:
shoes.cpp:19:24: note:   candidate expects 3 arguments, 1 provided
         return (count(r) - count(l - 1));
                        ^
shoes.cpp:19:39: error: no matching function for call to 'count(int)'
         return (count(r) - count(l - 1));
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from shoes.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:4076:5: note: candidate: template<class _IIter, class _Tp> typename std::iterator_traits<_Iterator>::difference_type std::count(_IIter, _IIter, const _Tp&)
     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
     ^~~~~
/usr/include/c++/7/bits/stl_algo.h:4076:5: note:   template argument deduction/substitution failed:
shoes.cpp:19:39: note:   candidate expects 3 arguments, 1 provided
         return (count(r) - count(l - 1));
                                       ^