Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- private static long totalComponents = 0;
- public static void main(String[] args) {
- /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
- Scanner in = new Scanner(System.in);
- int count = Integer.parseInt(in.nextLine());
- long[] array = new long[count];
- String[] pieces = in.nextLine().split(" ");
- for(int i = 0; i < count; i++)
- array[i] = Long.parseLong(pieces[i]);
- combine(array);
- totalComponents += 64;
- System.out.println(totalComponents);
- }
- private static void combine(int nextIndex, int bufIndex, long[] input, long[] buffer)
- {
- if(nextIndex == input.length)
- return;
- for(int i = nextIndex; i < input.length; i++)
- {
- buffer[bufIndex] = input[i];
- addComponentsForSet(buffer, bufIndex);
- combine(i+1, bufIndex+1, input, buffer);
- }
- }
- private static void combine(long[] input)
- {
- int nextIndex = 0;
- int bufIndex = 0;
- long[] buffer = new long[input.length];
- combine(nextIndex, bufIndex, input, buffer);
- }
- private static void addComponentsForSet(long[] buffer, int bufIndex)
- {
- List<Long> connected = new ArrayList<Long>();
- connected.add(buffer[0]);
- Set<Integer> overlaps = new HashSet<Integer>();
- for(int i = 1; i <= bufIndex; i++) {
- long next = buffer[i];
- overlaps.clear();
- for(int j = 0; j < connected.size(); j++)
- if( (connected.get(j) & next) != 0) overlaps.add(j);
- Iterator<Long> it = connected.iterator();
- int idx = 0;
- while(it.hasNext()) {
- long component = it.next();
- if(overlaps.contains(idx)) {
- it.remove();
- next = next | component;
- }
- }
- connected.add(next);
- }
- totalComponents += 64;
- for(Long component : connected) {
- int ones = getNumOnes(component);
- if(ones > 1)
- totalComponents = totalComponents - ones +1;
- }
- }
- private static int getNumOnes(long n) {
- int numOnes = 0;
- for(int i = 0; i <= 63; i++) {
- if((n >> i) == 0) return numOnes;
- if( ((n >> i) & 1) == 1)
- numOnes++;
- }
- return numOnes;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement