fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8.  
  9. public class Main {
  10.     public static void main(String[] args) {
  11.  
  12.         Scanner sc = new Scanner(System.in);
  13.  
  14.         int n = sc.nextInt();
  15.         int[] A = new int[n];
  16.         int[] B = new int[n];
  17.  
  18.         for (int i = 0; i < n; i++)
  19.            A[i] = sc.nextInt();
  20.         for (int i = 0; i < n; i++)
  21.            B[i] = sc.nextInt();
  22.  
  23.  
  24.         List<Integer> badPos = new ArrayList<>();
  25.         List<Integer> goodPos = new ArrayList<>();
  26.  
  27.         for (int i = 0; i < n; i++) {
  28.             if (A[i] == B[i]) badPos.add(i);
  29.             else goodPos.add(i);
  30.         }
  31.  
  32.         //no conflicts → no swaps
  33.         if (badPos.size() == 0) {
  34.             System.out.println(0);
  35.             return;
  36.         }
  37.  
  38.         //count how many times each value appears in bad positions
  39.         Map<Integer, Integer> freq = new HashMap<>();
  40.         for (int idx : badPos) {
  41.             freq.put(A[idx], freq.getOrDefault(A[idx], 0) + 1);
  42.         }
  43.  
  44.         //max heap → always solve most problematic duplicate first
  45.         PriorityQueue<int[]> pq = new PriorityQueue<>(
  46.                 (x, y) -> y[1] - x[1]     // sort by frequency desc
  47.         );
  48.  
  49.         for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
  50.             pq.add(new int[]{ e.getKey(), e.getValue() });
  51.         }
  52.  
  53.         int swaps = 0;
  54.  
  55.         //pair off the two most frequent values repeatedly
  56.         while (pq.size() > 1) {
  57.             int[] a = pq.poll();
  58.             int[] b = pq.poll();
  59.  
  60.             swaps++;       //one swap fixes 2 conflict occurrences
  61.             a[1]--;
  62.             b[1]--;
  63.  
  64.             if (a[1] > 0) pq.add(a);
  65.             if (b[1] > 0) pq.add(b);
  66.         }
  67.  
  68.         //leftover → only one value remains to fix
  69.         if (pq.isEmpty()) {
  70.             System.out.println(swaps);
  71.             return;
  72.         }
  73.  
  74.         int[] left = pq.poll();
  75.         int need = left[1];   // how many unsolved bad occurrences remain
  76.         int v = left[0];      // the leftover value
  77.  
  78.         //place these remaining occurrences into good positions
  79.         for (int g : goodPos) {
  80.             if (need == 0) break;
  81.  
  82.             //avoid swapping into a position that becomes bad again
  83.             if (A[g] == v) continue;
  84.             if (B[g] == v) continue;
  85.  
  86.             swaps++;
  87.             need--;
  88.         }
  89.  
  90.         // if still leftover → impossible 
  91.         if (need > 0) {
  92.             System.out.println(-1);
  93.         } else {
  94.             System.out.println(swaps);
  95.         }
  96.     }
  97. }
Success #stdin #stdout 0.14s 56644KB
comments (?)
stdin
copy 
5
1 5 3 1 3
1 5 3 5 1
stdout
copy 
2
https://ideone.com/zNNDdW
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!