Advertisement
Guest User

Untitled

a guest
Jan 28th, 2015
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. public class Solution {
  2.  
  3. private static long totalComponents = 0;
  4.  
  5. public static void main(String[] args) {
  6. /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
  7. Scanner in = new Scanner(System.in);
  8. int count = Integer.parseInt(in.nextLine());
  9. long[] array = new long[count];
  10. String[] pieces = in.nextLine().split(" ");
  11. for(int i = 0; i < count; i++)
  12. array[i] = Long.parseLong(pieces[i]);
  13. combine(array);
  14. totalComponents += 64;
  15. System.out.println(totalComponents);
  16. }
  17.  
  18. private static void combine(int nextIndex, int bufIndex, long[] input, long[] buffer)
  19. {
  20. if(nextIndex == input.length)
  21. return;
  22. for(int i = nextIndex; i < input.length; i++)
  23. {
  24. buffer[bufIndex] = input[i];
  25. addComponentsForSet(buffer, bufIndex);
  26. combine(i+1, bufIndex+1, input, buffer);
  27. }
  28. }
  29.  
  30. private static void combine(long[] input)
  31. {
  32. int nextIndex = 0;
  33. int bufIndex = 0;
  34. long[] buffer = new long[input.length];
  35. combine(nextIndex, bufIndex, input, buffer);
  36. }
  37.  
  38. private static void addComponentsForSet(long[] buffer, int bufIndex)
  39. {
  40. List<Long> connected = new ArrayList<Long>();
  41. connected.add(buffer[0]);
  42. Set<Integer> overlaps = new HashSet<Integer>();
  43.  
  44. for(int i = 1; i <= bufIndex; i++) {
  45. long next = buffer[i];
  46. overlaps.clear();
  47. for(int j = 0; j < connected.size(); j++)
  48. if( (connected.get(j) & next) != 0) overlaps.add(j);
  49.  
  50. Iterator<Long> it = connected.iterator();
  51. int idx = 0;
  52. while(it.hasNext()) {
  53. long component = it.next();
  54. if(overlaps.contains(idx)) {
  55. it.remove();
  56. next = next | component;
  57. }
  58. }
  59. connected.add(next);
  60. }
  61.  
  62. totalComponents += 64;
  63. for(Long component : connected) {
  64. int ones = getNumOnes(component);
  65. if(ones > 1)
  66. totalComponents = totalComponents - ones +1;
  67. }
  68. }
  69.  
  70. private static int getNumOnes(long n) {
  71. int numOnes = 0;
  72. for(int i = 0; i <= 63; i++) {
  73. if((n >> i) == 0) return numOnes;
  74. if( ((n >> i) & 1) == 1)
  75. numOnes++;
  76. }
  77. return numOnes;
  78. }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement