Advertisement
Guest User

Untitled

a guest
Dec 13th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.23 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement