fork download
copy 
  1.  
  2. #include <algorithm>
  3. #include <utility>
  4. #include <map>
  5. #include <set>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef long double ld;
  11.  
  12. #define lsb(x) (x&-x)
  13. #define msb(x) (1 << (31-clz(x)))
  14. #define clz(x) __builtin_clz(x)
  15. #define ctz(x) __builtin_ctz(x)
  16. #define popcount(x) __builtin_popcount(x)
  17.  
  18. #define scan_type(t,fmt) int scan(t &x){return scanf(fmt, &x);}
  19. #define print_type(t,fmt) int print(t const&x){return printf(fmt, x);}
  20. #define println_type(t,fmt) int println(t const&x){return printf(fmt"\n", x);}
  21. #define def_type(t, fmt) scan_type(t,fmt) print_type(t,fmt) println_type(t,fmt)
  22.  
  23. def_type(int, "%d");
  24. def_type(ll, "%lld");
  25. def_type(ull, "%llu");
  26. def_type(float, "%f");
  27. def_type(double, "%lf");
  28. def_type(char, "%c");
  29. // def_type(char *, "%s");
  30.  
  31. #include <bits/stdc++.h>
  32.  
  33. int const N = 1e5;
  34. int n, m;
  35.  
  36. struct node {
  37.   int key, id;
  38.   node *l, *r = l = nullptr;
  39.  
  40.   node(int k, int i) {
  41.     key = k;
  42.     id = i;
  43.   }
  44.  
  45.   ~node() {
  46.     if (l)
  47.       delete l;
  48.     if (r)
  49.       delete r;
  50.   }
  51. };
  52.  
  53. node *root = nullptr;
  54. char h[int (10e6) + 16];
  55.  
  56. void insert(int x, int id) {
  57.   if (root == nullptr) {
  58.     root = new node(x, id);
  59.     return;
  60.   }
  61.  
  62.   auto p = root;
  63.   int i = 0;
  64.   bool okay = false;
  65.   while (!okay)
  66.     if (p->id != id)
  67.       p->id = id, p->key = x, okay = true;
  68.     else if (h[i] ^= 1, i = i * 2 + 1, x < p->key)
  69.       if (p->l)
  70.         p = p->l;
  71.       else
  72.       	p->l = new node(x, id), okay = true;
  73.     else if (h[i] ^= 2, i = i * 2 + 2, x >= p->key)
  74.       if (p->r)
  75.       	p = p->r;
  76.       else
  77. 	      p->r = new node(x, id), okay = true;
  78. }
  79.  
  80. int main() {
  81.   scan(n), scan(m);
  82.   fill(h, h + int (10e6), '0');
  83.   map < string, bool > mm;
  84.   while (n--) {
  85.     for (int i = 0; i < m; ++i) {
  86.       int x;
  87.       scan(x);
  88.       insert(x, n);
  89.     }
  90.     mm[h] = true;
  91.     fill(h, h + int (10e6), '0');
  92.   }
  93.  
  94.   println(int (mm.size()));
  95. }
Success #stdin #stdout 0.17s 13232KB
comments (?)
stdin
copy 
5 3
2 7 1
3 1 4
1 5 9
2 6 5
9 7 3
stdout
copy 
4
https://ideone.com/keWRNu
language:
C++14 (gcc 8.3)
created:
8 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!