fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
  14. template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(NULL);
  20.  
  21.     int n;
  22.     cin >> n;
  23.     vector<array<int, 2>> trie(1);
  24.     vector<int> cnt(1);
  25.     for (int i=0; i<n; i++) {
  26.         string s;
  27.         cin >> s;
  28.  
  29.         uint32_t val = 0;
  30.         int last = 0;
  31.         for (int j=0; j<(int)s.size(); j++)
  32.             if (s[j] == '.' || s[j] == '/') {
  33.                 val = (val << 8) + stoi(s.substr(last, j - last));
  34.                 last = j + 1;
  35.             }
  36.         int u = 0, len = stoi(s.substr(s.find('/') + 1));
  37.         for (int j=31; j>=0 && len>0; j--, len--) {
  38.             int b = val >> j & 1;
  39.             if (!trie[u][b]) {
  40.                 trie[u][b] = (int) trie.size();
  41.                 trie.emplace_back();
  42.                 cnt.emplace_back();
  43.             }
  44.             u = trie[u][b];
  45.         }
  46.         cnt[u]++;
  47.     }
  48.  
  49.     auto dfs1 = [&] (auto &self, int u, int len, uint32_t val) -> void {
  50.         if (u == 0 && len > 0)
  51.             return;
  52.         self(self, trie[u][0], len + 1, val << 1);
  53.         self(self, trie[u][1], len + 1, (val << 1) + 1);
  54.         if (cnt[trie[u][0]] > 0 && cnt[trie[u][1]] > 0)
  55.             cnt[u]++;
  56.     };
  57.  
  58.     auto dfs2 = [&] (auto &self, int u, int len, uint32_t val) -> void {
  59.         if (u == 0 && len > 0)
  60.             return;
  61.         if (cnt[u] > 0) {
  62.             uint32_t cur = val << (32 - len);
  63.             string ret = '/' + to_string(len);
  64.             for (int rep=0; rep<4; rep++) {
  65.                 ret = '.' + to_string(cur % 256) + ret;
  66.                 cur >>= 8;
  67.             }
  68.             cout << ret.substr(1) << "\n";
  69.             return;
  70.         }
  71.         self(self, trie[u][0], len + 1, val << 1);
  72.         self(self, trie[u][1], len + 1, (val << 1) + 1);
  73.     };
  74.  
  75.     dfs1(dfs1, 0, 0, 0);
  76.     dfs2(dfs2, 0, 0, 0);
  77.  
  78.     return 0;
  79. }
  80.  
Runtime error #stdin #stdout #stderr 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi
https://ideone.com/HuFtnH
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

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!