Submission #152576

#	Time	Username	Problem	Language	Result	Execution time	Memory
152576		Myldero	Arranging Shoes (IOI19_shoes)	Java	100 / 100	409 ms	36380 KiB

shoes

import java.io.*;
import java.util.*;
import java.math.*;

class shoes {

    int[] s;
    int n, m;

    int[] positions, pairs;
    boolean[] visited;
    Fenwick tree;

    public long count_swaps(int[] S) {
        s = S;
        m = s.length;
        n = m / 2;

        positions = new int[m];
        pairs = new int[m];
        visited = new boolean[m];

        tree = new Fenwick(m);
        for (int i = 1; i <= m; i++) {
            tree.update(i, 1);
        }

        matchPairs();

        long sum = 0;

        for (int i = m-1; i >= 1; i--) {
            if (visited[i]) continue;
            int a = pairs[i];
            int posA = tree.get(a+1);
            int posB = tree.get(i+1);

            sum += posB - posA - 1;
            tree.update(a+1, -1);

            visited[a] = true;

            if (s[a] > s[i]) sum++;
        }

        return sum;
    }

    void matchPairs () {
        ArrayList<Integer>[] a = new ArrayList[n+1];
        ArrayList<Integer>[] b = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            a[i] = new ArrayList<Integer>();
            b[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            if (s[i] < 0) {
                a[-s[i]].add(i);
            } else {
                b[s[i]].add(i);
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < a[i].size(); j++) {
                pairs[a[i].get(j)] = b[i].get(j);
                pairs[b[i].get(j)] = a[i].get(j);
            }
        }

    }
}

class Fenwick {
    int n;
    int[] arr;

    public Fenwick (int n) {
        this.n = n;
        arr = new int[n+1];
    }

    public int lsb (int a) {
        return a & -a;
    }

    public void update (int idx, int value) {
        while (idx <= n) {
            arr[idx] += value;
            idx += lsb(idx);
        }
    }

    public int get (int idx) {
        int sum = 0;

        while (idx > 0) {
            sum += arr[idx];
            idx -= lsb(idx);
        }
        return sum;
    }

}

Compilation message (stderr)

Note: shoes.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15