daily pastebin goal
58%
SHARE
TWEET

Untitled

a guest Dec 13th, 2018 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. #include <sys/types.h>
  6. #include <sys/stat.h>
  7. #include <fcntl.h>
  8. #include <unistd.h>
  9. #include <string.h>
  10.  
  11. static constexpr int MEMORY_SIZE = 10;
  12.  
  13. enum class Direction { AWAY = 0, LEFT = 1, RIGHT = 2, UP = 3, DOWN = 4, SAME = 5 };
  14.  
  15. using std::cin;
  16. using std::cerr;
  17. using std::cout;
  18. using std::endl;
  19. using std::vector;
  20. using std::sort;
  21.  
  22. struct Position
  23. {
  24.     int x{}, y{};
  25. };
  26.  
  27. struct CopterState
  28. {
  29.     Direction dir{Direction::AWAY};
  30.     unsigned char mem[MEMORY_SIZE]{};
  31. };
  32.  
  33. unsigned get_value(unsigned char *mem)
  34. {
  35.     return mem[0] | (mem[1] << 8) | (mem[2] << 16) | (mem[3] << 24);
  36. }
  37.  
  38. void random_bytes(unsigned char *mem, size_t size)
  39. {
  40.     static int fd = -1;
  41.     if (fd < 0) {
  42.         fd = open("/dev/urandom", O_RDONLY, 0);
  43.         if (fd < 0) {
  44.             cerr << "cannot open /dev/urandom" << endl;
  45.             abort();
  46.         }
  47.     }
  48.     ssize_t sz = read(fd, mem, size);
  49.     if (sz < 0) {
  50.         cerr << "read error from /dev/urandom" << endl;
  51.         abort();
  52.     }
  53.     if (!sz) {
  54.         cerr << "EOF from /dev/urandom" << endl;
  55.         abort();
  56.     }
  57.     if (sz != (ssize_t) size) {
  58.         cerr << "invalid read from /dev/urandom" << endl;
  59.         abort();
  60.     }
  61. }
  62.  
  63.  
  64.    
  65. int main()
  66. {
  67.     int copter_count;
  68.     cin >> copter_count;
  69.  
  70.     if (copter_count <= 0 || copter_count > 1000) {
  71.         cerr << "invalid copter count" << endl;
  72.         abort();
  73.     }
  74.  
  75.     vector<Position> targets(copter_count);
  76.     for (int i = 0; i < copter_count; ++i) {
  77.         int x, y;
  78.         cin >> x >> y;
  79.         targets[i] = {x, y};
  80.     }
  81.  
  82.     CopterState self{};
  83.    
  84.     for (int i = 0; i < MEMORY_SIZE; ++i) {
  85.         int m;
  86.         cin >> m;
  87.         if (m < 0 || m > 255) {
  88.             cerr << "invalid memory value" << endl;
  89.             abort();
  90.         }
  91.         self.mem[i] = m;
  92.     }
  93.  
  94.     int neighbour_count;
  95.     cin >> neighbour_count;
  96.     if (neighbour_count < 0 || neighbour_count >= copter_count) {
  97.         cerr << "invalid neighbour count " << neighbour_count << endl;
  98.         abort();
  99.     }
  100.     vector<CopterState> neighbours(neighbour_count);
  101.     for (int i = 0; i < neighbour_count; ++i) {
  102.         int dir;
  103.         cin >> dir;
  104.         if (dir < int(Direction::LEFT) || dir > int(Direction::SAME)) {
  105.             cerr << "invalid direction for neighbour " << i << endl;
  106.             abort();
  107.         }
  108.         neighbours[i].dir = Direction(dir);
  109.         for (int j = 0; j < MEMORY_SIZE; ++j) {
  110.             int m;
  111.             cin >> m;
  112.             if (m < 0 || m > 255) {
  113.                 cerr << "invalid memory value" << endl;
  114.                 abort();
  115.             }
  116.             neighbours[i].mem[j] = m;
  117.         }
  118.     }
  119.  
  120.     if (self.mem[0] == 0) {
  121.         // initial state
  122.         self.mem[0] = 1;
  123.         random_bytes(self.mem + 1, 4);
  124.         self.dir = Direction::SAME;
  125.         self.mem[5] = int(Direction::AWAY);
  126.         memcpy(&self.mem[6], &self.mem[1], 4);
  127.     } else if (self.mem[0] >= 1 && self.mem[0] < copter_count) {
  128.         // propagation state
  129.         unsigned cur = get_value(self.mem + 6);
  130.         int max_ind = -1;
  131.         unsigned max_val = cur;
  132.         for (int i = 0; i < neighbour_count; ++i) {
  133.             unsigned n = get_value(neighbours[i].mem + 6);
  134.             if (n > max_val) {
  135.                 max_val = n;
  136.                 max_ind = i;
  137.             }
  138.         }
  139.         if (max_ind >= 0) {
  140.             memcpy(self.mem + 6, neighbours[max_ind].mem + 6, 4);
  141.             self.mem[5] = int(neighbours[max_ind].dir);
  142.         }
  143.         ++self.mem[0];
  144.         self.dir = Direction::SAME;
  145.     } else if (self.mem[0] >= copter_count && self.mem[0] <= copter_count * 2) {
  146.         // movement state
  147.         int new_dir = int(Direction::SAME);
  148.         if (self.mem[5] == int(Direction::LEFT)
  149.             || self.mem[5] == int(Direction::RIGHT)
  150.             || self.mem[5] == int(Direction::UP)
  151.             || self.mem[5] == int(Direction::DOWN)) {
  152.             int i;
  153.             for (i = 0; i < neighbour_count; ++i) {
  154.                 if (int(neighbours[i].dir) == self.mem[5]) {
  155.                     new_dir = int(neighbours[i].mem[5]);
  156.                     break;
  157.                 }
  158.             }
  159.             if (i >= neighbour_count) {
  160.                 cerr << "no neighbour in the given direction" << endl;
  161.                 abort();
  162.             }
  163.             self.dir = Direction(self.mem[5]);
  164.             self.mem[5] = new_dir;
  165.         } else {
  166.             self.dir = Direction::SAME;
  167.         }
  168.         ++self.mem[0];
  169.     } else if (self.mem[0] == copter_count * 2 + 1) {
  170.         // ensure, that all copters are at the same point
  171.         if (neighbour_count + 1 != copter_count) {
  172.             cerr << "not all copters at the same point" << endl;
  173.             abort();
  174.         }
  175.         // sort random numbers and assign serial to each copter
  176.         vector<unsigned> copter_ids(copter_count);
  177.         for (int i = 0; i < neighbour_count; ++i) {
  178.             copter_ids[i] = get_value(neighbours[i].mem + 1);
  179.         }
  180.         unsigned self_id = get_value(self.mem + 1);
  181.         copter_ids[neighbour_count] = self_id;
  182.         sort(copter_ids.begin(), copter_ids.end());
  183.         memset(self.mem + 5, 0, 5);
  184.         int i;
  185.         for (i = 0; i < int(copter_ids.size()); ++i) {
  186.             if (self_id == copter_ids[i]) {
  187.                 break;
  188.             }
  189.         }
  190.         if (i >= int(copter_ids.size())) {
  191.             cerr << "copter_id not found" << endl;
  192.             abort();
  193.         }
  194.         self.mem[5] = i + 1;
  195.  
  196.         // assign target from the list
  197.         // assume all copters are not at the first target point
  198.         int diff_x = targets[i].x - targets[0].x;
  199.         int diff_y = targets[i].y - targets[0].y;
  200.         if ((short) diff_x != diff_x) {
  201.             cerr << "target figure is too big" << endl;
  202.             abort();
  203.         }
  204.         if ((short) diff_y != diff_y) {
  205.             cerr << "target figure is too big" << endl;
  206.             abort();
  207.         }
  208.         self.mem[6] = diff_x;
  209.         self.mem[7] = diff_x >> 8;
  210.         self.mem[8] = diff_y;
  211.         self.mem[9] = diff_y >> 8;
  212.  
  213.         ++self.mem[0];
  214.         self.dir = Direction::SAME;
  215.     } else {
  216.         // extract direction
  217.         int diff_x = (short)(self.mem[6] | self.mem[7] << 8);
  218.         int diff_y = (short)(self.mem[8] | self.mem[9] << 8);
  219.         if (diff_x < 0) {
  220.             self.dir = Direction::LEFT;
  221.             ++diff_x;
  222.         } else if (diff_x > 0) {
  223.             self.dir = Direction::RIGHT;
  224.             --diff_x;
  225.         } else if (diff_y < 0) {
  226.             self.dir = Direction::DOWN;
  227.             ++diff_y;
  228.         } else if (diff_y > 0) {
  229.             self.dir = Direction::UP;
  230.             --diff_y;
  231.         } else {
  232.             self.dir = Direction::SAME;
  233.         }
  234.         self.mem[6] = diff_x;
  235.         self.mem[7] = diff_x >> 8;
  236.         self.mem[8] = diff_y;
  237.         self.mem[9] = diff_y >> 8;
  238.     }
  239.  
  240.     if (self.dir == Direction(0)) {
  241.         cerr << "copter does not make a turn" << endl;
  242.         abort();
  243.     }
  244.  
  245.     std::cout << int(self.dir);
  246.     for (int i = 0; i < 10; ++i) {
  247.         std::cout << " " << int(self.mem[i]);
  248.     }
  249.     cout << endl;
  250. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top