Submission #144819

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

shoes

#include <bits/stdc++.h>

using namespace std;

using lint = long long;

const int maxn = 1e5 + 9;

struct fenwick {
    vector<lint> tree;
    fenwick(int _n) : tree(_n + 1, 0) {}
    lint get(int index) {
        lint sum = 0LL;
        while (0 < index) {
            sum += tree[index] * 1LL;
            index -= (index & -index);
        }
        return sum * 1LL;
    }
    void add(int index, lint value) {
        while (index < tree.size()) {
            tree[index] += value * 1LL;
            index += (index & -index);
        }
    }
};

lint count_swaps(vector<int> s) {
    int n = (int)s.size() / 2;
    vector<bool> check(n * 2, false);
    fenwick tree(n * 2);
    priority_queue<int> pq1[maxn], pq2[maxn];
    lint answer = 0LL;
    for (int i = 0; i < 2 * n; ++i) {
        if (s[i] > 0)
            pq1[s[i]].push(-i);
        else
            pq2[-s[i]].push(-i);
        tree.add(i + 1, 1LL);
    }
    for (int i = 0; i < 2 * n; ++i) {
        if (check[i])
            continue;
        int pos;
        if (s[i] > 0) {
            pos = -pq2[s[i]].top();
            pq2[s[i]].pop(); pq1[s[i]].pop();
            ++answer;
        } else {
            pos = -pq1[-s[i]].top();
            pq1[-s[i]].pop(); pq2[-s[i]].pop();
        }
        tree.add(i + 1, -1);
        tree.add(pos + 1, -1);
        answer += (tree.get(pos + 1) * 1LL - tree.get(i) * 1LL) * 1LL;
        check[i] = check[pos] = true;
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<int> test = {3, -1, 2, -2, 1, -3};
    cout << count_swaps(test) << '\n';
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwick::add(int, lint)':
shoes.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (index < tree.size()) {
                ~~~~~~^~~~~~~~~~~~~
/tmp/ccsl8IFQ.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc9BrXmC.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status