Advertisement
he_obviously

Untitled

Oct 4th, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <map>
  5. #include <unordered_set>
  6. #include <unordered_map>
  7.  
  8. using namespace std;
  9.  
  10. int gcd(int a, int b) {
  11.     return b ? gcd(b, a % b) : a;
  12. }
  13.  
  14. int n, sz;
  15. vector<pair<int, int> > d;
  16. map<pair<int, int>, int> num;
  17. vector<bool> used;
  18. vector<int> dx, dy;
  19.  
  20. void check(int i) {
  21.     used[i] = true;
  22.     int x = d[i].first, y = d[i].second;
  23.     for (int j = 0; j < 8; ++j) {
  24.         if (x + dx[j] > 0 && x + dx[j] <= n && y + dy[j] > 0 && y + dy[j] <= n &&
  25.             gcd(x + dx[j], y + dy[j]) == 1) {
  26.             check(num[{x + dx[j], y + dy[j]}]);
  27.         }
  28.     }
  29. }
  30.  
  31. void dfs(int i) {
  32.     used[i] = true;
  33.     int x = d[i].first, y = d[i].second;
  34.     cout << x << "/" << y << " ";
  35.     for (int j = 0; j < 8; ++j) {
  36.         if (x + dx[j] > 0 && x + dx[j] <= n && y + dy[j] > 0 && y + dy[j] <= n &&
  37.             gcd(x + dx[j], y + dy[j]) == 1) {
  38.             dfs(num[{x + dx[j], y + dy[j]}]);
  39.         }
  40.     }
  41. }
  42.  
  43. int main() {
  44.  
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0); cout.tie(0);
  47.  
  48.     cin >> n;
  49.  
  50.     dx.resize(8);
  51.     dx[0] = -2;
  52.     dx[1] = -2;
  53.     dx[2] = -1;
  54.     dx[3] = -1;
  55.     dx[4] = 1;
  56.     dx[5] = 1;
  57.     dx[6] = 2;
  58.     dx[7] = 2;
  59.  
  60.     dy.resize(8);
  61.     dy[0] = -1;
  62.     dy[1] = 1;
  63.     dy[2] = -2;
  64.     dy[3] = 2;
  65.     dy[4] = -2;
  66.     dy[5] = 2;
  67.     dy[6] = -1;
  68.     dy[7] = 1;
  69.  
  70.     for (int i = 1; i <= n; ++i) {
  71.         for (int j = 1; j <= n; ++j) {
  72.             int x = i / gcd(i, j),
  73.                 y = j / gcd(i, j);
  74.             if (num.find({ x, y }) == num.end()) {
  75.                 d.push_back({ x, y });
  76.                 num[{x, y}] = (int)d.size() - 1;
  77.             }
  78.         }
  79.     }
  80.  
  81.     sz = (int)d.size();
  82.  
  83.     used.resize(sz, false);
  84.  
  85.     check(0);
  86.  
  87.     for (int i = 0; i < sz; ++i) {
  88.         if (!used[i]) {
  89.             cout << -1;
  90.             return 0;
  91.         }
  92.     }
  93.  
  94.     fill(used.begin(), used.end(), false);
  95.  
  96.     dfs(0);
  97.  
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement