1590 - IP Networks

All about problems in Volume 15. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

1590 - IP Networks

Post by brianfry713 » Fri Sep 05, 2014 12:32 am

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Re: 1590 - IP Networks

Post by 20717TZ » Sun Jul 08, 2018 5:02 am

Get wrong answer, really don't know where the code fails for which special cases? :oops:

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;
}

I Believe I Can - leestime.com

Post Reply

Return to “Volume 15 (1500-1599)”