fork download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Created to solve http://c...content-available-to-author-only...e.com/q/23461/16293
  5.  * and submitted as http://c...content-available-to-author-only...e.com/a/23467/16293
  6.  */
  7. class EqualSums {
  8.  
  9.     public static void main(String[] args) {
  10.         final Scanner s = new Scanner(System.in);
  11.         // Read number of elements to divide
  12.         final int count = s.nextInt();
  13.         if (count % 2 == 1) {
  14.             throw new IllegalStateException(count + " can not be divided by 2. Consider adding a 0 value.");
  15.         }
  16.         // Read the elements to divide
  17.         final SortedList valueStack = new SortedList(count);
  18.         for (int i = 0; i < count; i++) {
  19.             valueStack.add(s.nextLong());
  20.         }
  21.  
  22.         final SortedList targetOne = new SortedList(count / 2);
  23.         final SortedList targetTwo = new SortedList(count / 2);
  24.         // Divide elements into two groups
  25.         addInPairs(targetOne, targetTwo, valueStack);
  26.         // Try to ensure groups have equal value
  27.         retaliate(targetOne, targetTwo);
  28.  
  29.         // Output result
  30.         System.out.println(targetOne);
  31.         System.out.println(targetTwo);
  32.         System.out.println("diff=" + Math.abs(targetOne.getSum() - targetTwo.getSum()));
  33.     }
  34.  
  35.     private static void addInPairs(SortedList targetOne, SortedList targetTwo, SortedList valueStack) {
  36.         SortedList smallerTarget = targetOne;
  37.         SortedList biggerTarget = targetTwo;
  38.         while (!valueStack.isEmpty()) {
  39.             // Add biggest remaining value to small target
  40.             smallerTarget.add(valueStack.removeLast());
  41.  
  42.             // Add second biggest remaining value to big target
  43.             biggerTarget.add(valueStack.removeLast());
  44.  
  45.             // Flip targets if roles have changed
  46.             if (smallerTarget.getSum() > biggerTarget.getSum()) {
  47.                 final SortedList temp = smallerTarget;
  48.                 smallerTarget = biggerTarget;
  49.                 biggerTarget = temp;
  50.             }
  51.         }
  52.  
  53.     }
  54.  
  55.     private static void retaliate(SortedList targetOne, SortedList targetTwo) {
  56.         long difference;
  57.         boolean changed;
  58.         outer:
  59.         do {
  60.             difference = Math.abs(targetOne.getSum() - targetTwo.getSum());
  61.             if (difference == 0) {
  62.                 return;
  63.             }
  64.             changed = false;
  65.             // Try to find two values, that reduce the difference by changing them between targets
  66.             for (Long valueOne : targetOne) {
  67.                 for (Long valueTwo : targetTwo) {
  68.                     final Long tempOne = targetOne.getSum() + valueTwo - valueOne;
  69.                     final Long tempTwo = targetTwo.getSum() - valueTwo + valueOne;
  70.                     if (Math.abs(tempOne - tempTwo) < difference) {
  71.                         targetOne.remove(valueOne);
  72.                         targetTwo.add(valueOne);
  73.                         targetTwo.remove(valueTwo);
  74.                         targetOne.add(valueTwo);
  75.                         changed = true;
  76.                         continue outer;
  77.                     }
  78.                 }
  79.             }
  80.         } while (changed);
  81.     }
  82.  
  83.     public static class SortedList extends AbstractList<Long> {
  84.  
  85.         private final ArrayList<Long> list;
  86.         private long sum = 0;
  87.  
  88.         public SortedList(int count) {
  89.             list = new ArrayList<>(count);
  90.         }
  91.  
  92.         // the next functions access list-field directly
  93.         @Override
  94.         public Long get(int index) {
  95.             return list.get(index);
  96.         }
  97.  
  98.         @Override
  99.         public boolean add(final Long t) {
  100.             final int i = Collections.binarySearch(list, t);
  101.             if (i < 0) {
  102.                 // No equal element present
  103.                 list.add(-i - 1, t);
  104.             } else {
  105.                 list.add(afterLastEqual(i, t), t);
  106.             }
  107.             sum += t;
  108.             return true;
  109.         }
  110.  
  111.         @Override
  112.         public Long remove(int index) {
  113.             final Long old = list.remove(index);
  114.             sum -= old;
  115.             return old;
  116.         }
  117.  
  118.         @Override
  119.         public int size() {
  120.             return list.size();
  121.         }
  122.  
  123.         // the next functions access list-field only through the functions above this point
  124.         // to ensure the sum is well kept
  125.  
  126.         public long getSum() {
  127.             return sum;
  128.         }
  129.  
  130.         private int afterLastEqual(final int start, Object o) {
  131.             int found = start;
  132.             while (found < size() && o.equals(get(found))) {
  133.                 found++;
  134.             }
  135.             return found;
  136.         }
  137.  
  138.         private int beforeFirstEqual(final int start, final Object o) {
  139.             int found = start;
  140.             while (found >= 0 && o.equals(get(found))) {
  141.                 found--;
  142.             }
  143.             return found;
  144.         }
  145.  
  146.         @Override
  147.         public int indexOf(Object o) {
  148.             try {
  149.                 final int i = Collections.binarySearch(this, (Long) o);
  150.                 if (i >= 0) {
  151.                     return beforeFirstEqual(i, o) + 1;
  152.                 }
  153.             } catch (ClassCastException e) {
  154.                 // Object was not instance of Long
  155.             }
  156.             return -1;
  157.         }
  158.  
  159.         @Override
  160.         public int lastIndexOf(Object o) {
  161.             try {
  162.                 final int i = Collections.binarySearch(this, (Long) o);
  163.                 if (i >= 0) {
  164.                     return afterLastEqual(i, o) - 1;
  165.                 }
  166.             } catch (ClassCastException e) {
  167.                 // Object was not instance of Long
  168.             }
  169.             return -1;
  170.         }
  171.  
  172.         @Override
  173.         public boolean remove(Object o) {
  174.             if (o == null) {
  175.                 return false;
  176.             }
  177.             final int i = indexOf(o);
  178.             if (i >= 0) {
  179.                 remove(i);
  180.                 return true;
  181.             }
  182.             return false;
  183.         }
  184.  
  185.         public Long removeLast() {
  186.             return remove(size() - 1);
  187.         }
  188.  
  189.         public Long removeFirst() {
  190.             return remove(0);
  191.         }
  192.  
  193.         @Override
  194.         public String toString() {
  195.             Iterator<Long> it = iterator();
  196.             if (!it.hasNext()) {
  197.                 return "";
  198.             }
  199.  
  200.             StringBuilder sb = new StringBuilder();
  201.             for (; ; ) {
  202.                 Long e = it.next();
  203.                 sb.append(e);
  204.                 if (!it.hasNext()) {
  205.                     return sb.toString();
  206.                 }
  207.                 sb.append(' ');
  208.             }
  209.         }
  210.     }
  211. }
  212.  
Success #stdin #stdout 0.11s 380672KB
comments (?)
stdin
copy 
4
1 2 3 4
stdout
copy 
1 4
2 3
diff=0
https://ideone.com/9Hf7dL
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

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!