Submission #850481

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

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int seg[1000000];

void build(int id, int l, int r) {
    if (l==r) {seg[id] = 0; return;}
    int mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    seg[id] = seg[id*2] + seg[id*2+1];
}

void update(int id, int l, int r, int target) {
    if (l>target||r<target) return;
    if (l==r) {seg[id] = 1; return;}
    // cout << "test3: " << id << endl;
    int mid = (l+r)/2;
    update(id*2, l, mid, target);
    update(id*2+1, mid+1, r, target);
    seg[id] = seg[id*2] + seg[id*2+1];
}

int sum(int id, int l, int r, int findl, int findr) {
    // cout << "test5: " << id << endl;
    if (findl<=l&&r<=findr) return seg[id];
    if (l>findr||r<findl) return 0;
    // cout << "test2: " << id << endl;
    int mid = (l+r)/2;
    return sum(id*2, l, mid, findl, findr) + sum(id*2+1, mid+1, r, findl, findr);
}

int count_swaps(vector<int> a) {
	int n = a.size()/2;
    // cout << n << endl;
    vector<int> left[n+1], right[n+1];
    for (int i=n*2-1;i>=0;i--) {
        if (a[i]<0) left[-a[i]].push_back(i);
        else right[a[i]].push_back(i);
    }
    build(1, 0, n*2-1);
    int ans = 0;
    vector<bool> done(2*n, false);
    int count = 0;
    for (int i=0;i<n*2;i++) {
        if (done[i]) continue;
        // cout << i << endl;
        int sz = abs(a[i]);
        if (a[i]<0) {
            int pos = right[sz].back();
            ans += pos - (count*2+1);
            // cout << "test1: " << ans << " " << pos << endl;
            ans += sum(1, 0, n*2-1, pos+1, n*2-1);
            done[pos] = true;
            update(1, 0, n*2-1, pos);
            // cout << "test4: " << ans << endl;
        } else {
            int pos = left[sz].back();
            ans += pos - count*2;
            // cout << "test1: " << ans << " " << pos << endl;
            ans += sum(1, 0, n*2-1, pos+1, n*2-1);
            done[pos] = true;
            update(1, 0, n*2-1, pos);
            // cout << "test4: " << ans << endl;
        }
        left[sz].pop_back();
        right[sz].pop_back();
        count++;
    }
    return ans;
}

// signed main() {
//     vector<int> v = {-2, 2, 2, -2, -2, 2};
//     cout << count_swaps(v) << endl;
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccIY1nrF.o: in function `main':
grader.cpp:(.text.startup+0x29d): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status