Submission #519939

#	Time	Username	Problem	Language	Result	Execution time	Memory
519939		vijay	Arranging Shoes (IOI19_shoes)	Java	100 / 100	525 ms	39040 KiB

shoes

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

public class shoes {
  int[] ft;
  int MAXN = 400001;
  public static void main(String[] args) throws IOException, FileNotFoundException {
    // Scanner in = new Scanner(new File("test.in"));
    // ioi19shoes i = new ioi19shoes();
    // System.out.println(i.count_swaps(new int[] {2, 1, -1, -2}));
  }

  public long count_swaps(int[] S){
    int N = S.length / 2;
    ft = new int[MAXN + 1];

    ArrayList<Integer>[] left = new ArrayList[N + 1];
    ArrayList<Integer>[] right = new ArrayList[N + 1];

    for(int i = 0; i <= N; i++){
      left[i] = new ArrayList<>();
      right[i] = new ArrayList<>();
    }

    for(int i = 0; i < 2*N; i++){
      if(S[i] < 0){
        left[-S[i]].add(i + 1);
      } else {
        right[S[i]].add(i + 1);
      }
    }

    long ans = 0;

    ArrayList<Pair> pairs = new ArrayList<>();

    for(int i = 1; i <= N; i++){
      for(int j = left[i].size() - 1; j >= 0; j--){
        int l = left[i].get(j);
        int r = right[i].get(j);
        if(l > r){
          ans++;
          int tmp = r;
          r = l;
          l = tmp;
        }
        pairs.add(new Pair(l, r));
      }
    }

    Collections.sort(pairs);

    for(Pair p: pairs){
      ans += query(MAXN) - query(p.left);
      ans += query(MAXN) - query(p.right);
      update(p.left, 1);
      update(p.right, 1);
    }

    return ans;
  }

  public class Pair implements Comparable<Pair> {
    int left, right;
    public Pair(int left, int right){
      this.left = left;
      this.right = right;
    }

    public int compareTo(Pair p){
      return left - p.left;
    }
  }

  public void update(int x, int v){while(x <= MAXN) {ft[x]+=v; x+=(x&-x);}}
  public int query(int x) {return x > 0 ? ft[x] + query(x-(x&-x)):0;}
}

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