OJ Board

Code: Select all

/* 1590 - IP Networks
      Author: Peter Lee
     Contact: leestime.com <at> gmail.com
   Algorithm: bitwise
       Notes: 
 */
#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
#define N 32
using namespace std;

// Look for which bit starts to be different
int GetStart(const vector<bitset<N>>& v) {
    int m = v.size();
    for (int k = N-1; k >= 0; --k) {
        bool b = v[0][k];
        for (int i = 1; i < m; ++i) {
            if (v[i][k] != b)
                return k;
        }
    }
    return -1;
}

void PrintIP(const bitset<N>& v) {
    unsigned long x = v.to_ulong();
    int a = x >> 24; x <<= 8; x >>= 8;
    int b = x >> 16; x <<= 16; x >>= 16;
    int c = x >> 8; x <<=24; x >>= 24;
    int d = x;
    printf("%d.%d.%d.%d\n", a, b, c, d);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    int m;
    while (1 == scanf("%d\n", &m)) {
        vector<bitset<N>> v;
        for (int i = 0; i < m; ++i) {
            int a, b, c, d;
            scanf("%d.%d.%d.%d\n", &a, &b, &c, &d);
            bitset<N> bs;
            bs |= (a << 24);
            bs |= (b << 16);
            bs |= (c << 8);
            bs |= d;
            v.push_back(bs);
        }
        
        int s = GetStart(v);
        bitset<N> mask(0);
        for (int k = N-1; k > s; --k)
            mask.set(k);
        
        PrintIP(mask & v[0]);
        PrintIP(mask);
    }

    return 0;
}