fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <ctime>
  5.  
  6. typedef unsigned short uint16_t;
  7. typedef unsigned char uint8_t;
  8.  
  9. struct trie {
  10.     unsigned int link[2048];
  11. };
  12.  
  13. uint8_t getData (int data, uint16_t& dir, uint16_t& pos, uint8_t& x) {
  14.     dir = (data >> 0)  & 0xffff;
  15.     pos = (data >> 16) & 0xffff;
  16.     x   =  pos / 32;
  17.     return pos % 32;
  18. }
  19. void insert(trie *root, int data) {
  20.     uint16_t dir, pos;
  21.     uint8_t x, y = getData(data, dir, pos, x);
  22.     root[dir].link[x] |= 1 << y;
  23. }
  24. bool find(trie *root, int data) {
  25.     uint16_t dir, pos;
  26.     uint8_t x, y = getData(data, dir, pos, x);
  27.     return root[dir].link[x] & (1 << y);
  28. }
  29. void remove(trie *root, int data) {
  30.     uint16_t dir, pos;
  31.     uint8_t x, y = getData(data, dir, pos, x);
  32.     root[dir].link[x] &= ~(1 << y);
  33. }
  34.  
  35. int main (int argc, char *argv[]) {
  36.     srand(time(NULL));
  37.     trie *root = new trie[65536];
  38.  
  39.     int input;
  40.     for (int i=0;i<10;i++) {
  41.         std::cin >> input;
  42.         insert(root, input);
  43.     }
  44.  
  45.     for (int i=0;i<10;i++) {
  46.         std::cin >> input;
  47.         std::cout << "The system " << (find(root, input) ? "found " : "did not find ") << 
  48.             "the number " << input << ".\n";
  49.     }
  50.  
  51.     std::cin >> input;
  52.     remove(root, input);
  53.     std::cout << "The system " << (find(root, input) ? "found " : "did not find ") << 
  54.             "the number " << input << ".\n";
  55.     std::cin >> input;
  56.     remove(root, input);
  57.     std::cout << "The system " << (find(root, input) ? "found " : "did not find ") << 
  58.             "the number " << input << ".\n";
  59.  
  60.     delete[] root;
  61.     return 0;
  62. }
Success #stdin #stdout 0s 2856KB
comments (?)
stdin
copy 
651
8
-185
98
18
98198165
849
321
6
0
18
9815
98198165
6
-185
981651
651
9815
618
984
18
-185
stdout
copy 
The system found the number 18.
The system did not find the number 9815.
The system found the number 98198165.
The system found the number 6.
The system found the number -185.
The system did not find the number 981651.
The system found the number 651.
The system did not find the number 9815.
The system did not find the number 618.
The system did not find the number 984.
The system did not find the number 18.
The system did not find the number -185.
https://ideone.com/McwWTV
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!