Submission #1188758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188758		orgiloogii	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define ll long long
using namespace std;

vector <ll> sum, a;
void build(int id, int l, int r){
    if(l == r){
        sum[id] = 1;
        return;
    }
    int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
    build(x, l, m);
    build(y, m + 1, r);
    sum[id] = sum[x] + sum[y];
}
void update(int id, int l, int r, int i){
    if(l == r){
        sum[id] = 0;
        return;
    }
    int m = (l + r) / 2, x = 2 * id + 1, y = x + 1;
    if(i <= m){
        update(x, l, m, i);
    }
    else{
        update(y, m + 1, r, i);
    }
    sum[id] = sum[x] + sum[y];
}

ll query(int id, int l, int r, int L, int R){
    if(L == l && r == R){
        return sum[id];
    }
    int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
    if(R <= m) return query(x, l, m, L, R);
    if(L >= m + 1) return query(y, m + 1, r, L, R);
    return query(x, l, m, L, m) + query(y, m + 1, r, m + 1, R);
}

long long count_swaps(vector<int> s) {
    int n = s.size();
    a.resize(n);
    sum.resize(4 * n, 0);
    for (int i = 0;i < n;i++) a[i] = s[i];
    vector <vector <int>> adj(n / 2 + 1), adj1(n / 2 + 1); //adj = eyreg, adj1 = surug;
    for (int i = 0;i < n;i++) {
        if (s[i] < 0) {
            adj1[-s[i]].push_back(i);
        }
        else {
            adj[s[i]].push_back(i);
        }
    }
    int id[n / 2 + 1] = {0};
    // for (int i = 0;i < n;i++) {
    //     if (s[i] < 0) {
    //         adj1[-s[i]].push_back(i);
    //     }
    //     else {
    //         adj[s[i]].push_back(i);
    //     }
    // }
    // for (int i = 0;i < adj.size();i++) {
    //     cout << i << ": ";
    //     for (auto x : adj[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    // for (int i = 0;i < adj1.size();i++) {
    //     cout << -i << ": ";
    //     for (auto x : adj1[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    bool vis[n] = {0};
    build(0, 0, n - 1);
    ll res = 0;
    for (int i = 0;i < n;i++) {
        if (!vis[i]) {
            if (s[i] < 0) {
                if (adj1[-s[i]][id[-s[i]]] + 1 == adj[-s[i]][id[-s[i]]]) {
                    vis[i] = true;
                    vis[i + 1] = true;
                    id[-s[i]]++;
                    continue;
                }
                res += query(0, 0, n - 1, adj1[-s[i]][id[-s[i]]] + 1, adj[-s[i]][id[-s[i]]] - 1);
                update(0, 0, n - 1, adj1[-s[i]][id[-s[i]]]);
                update(0, 0, n - 1, adj[-s[i]][id[-s[i]]]);
                vis[adj1[-s[i]][id[-s[i]]]] = true;
                vis[adj[-s[i]][id[-s[i]]]] = true;
                id[-s[i]]++;
            }
            else {
                if (adj1[s[i]][id[s[i]]] - 1 == adj[s[i]][id[s[i]]]) {
                    vis[i] = true;
                    vis[i + 1] = true;
                    id[s[i]]++;
                    res++;
                    continue;
                }
                res += query(0, 0, n - 1, adj[s[i]][id[s[i]]] + 1, adj1[s[i]][id[s[i]]] - 1) + 1;
                update(0, 0, n - 1, adj1[s[i]][id[s[i]]]);
                update(0, 0, n - 1, adj[s[i]][id[s[i]]]);
                vis[adj1[s[i]][id[s[i]]]] = true;
                vis[adj[s[i]][id[s[i]]]] = true;
                id[s[i]]++;
            }
        }
    }
    return res;
}
int main() {
    cout << count_swaps({-2, 2, 2, -2, -2, 2});
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccvcBssf.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccdW8rMA.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status