Submission #519660

#	Time	Username	Problem	Language	Result	Execution time	Memory
519660		vijay	Arranging Shoes (IOI19_shoes)	Java	10 / 100	76 ms	8596 KiB

shoes

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

public class shoes {
  int[] ft;
  int N;
  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){
    N = S.length;
    ft = new int[N + 1];
    HashMap<Integer, TreeSet<Integer>> hm = new HashMap<>();// stores right shoes
    int[] shoes = new int[N + 1];
    for(int i = 1; i <= N; i++){
      shoes[i] = S[i - 1];
      if(shoes[i] > 0){
        if(!hm.containsKey(shoes[i])){
          hm.put(shoes[i], new TreeSet<>());
        }
        hm.get(shoes[i]).add(i);
      }
    }
    // System.out.println(Arrays.toString(shoes));
    // System.out.println(hm);

    long sum = 0;

    for(int i = 1; i <= N; i++){
      if(shoes[i] < 0){

        // what is the nearest one?
        int idx = hm.get(-shoes[i]).first();
        // System.out.println("processing " + i + " " + shoes[i] + " " + idx);

        if(idx < i){
          // the right most point has a lesser value than the less most point
          int rright = idx + query(idx);
          // System.out.println("    rright: " + rright);
          int rcurr = i + query(i);
          // System.out.println("    rcurr: " + rcurr);
          sum += Math.abs(rright - rcurr);
          // whenever we move something away from this position, we bring it to another position
          update(i, -1);
          update(idx, 1);
        } else {
          int rright = idx + query(idx);
          // System.out.println("    rright: " + rright);
          int rcurr = i + query(i);
          // System.out.println("    rcurr: " + rcurr);
          sum += Math.abs((rright - 1) - rcurr); // rright - 1 is the target pt, minus rcurr
          update(i, -1);
          update(idx, 1);
        }


        hm.get(-shoes[i]).remove(idx);
      }
    }

    return sum;
  }

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

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