Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- int gcd(int a, int b) {
- return b ? gcd(b, a % b) : a;
- }
- int n, sz;
- vector<pair<int, int> > d;
- map<pair<int, int>, int> num;
- vector<bool> used;
- vector<int> dx, dy;
- void check(int i) {
- used[i] = true;
- int x = d[i].first, y = d[i].second;
- for (int j = 0; j < 8; ++j) {
- if (x + dx[j] > 0 && x + dx[j] <= n && y + dy[j] > 0 && y + dy[j] <= n &&
- gcd(x + dx[j], y + dy[j]) == 1) {
- check(num[{x + dx[j], y + dy[j]}]);
- }
- }
- }
- void dfs(int i) {
- used[i] = true;
- int x = d[i].first, y = d[i].second;
- cout << x << "/" << y << " ";
- for (int j = 0; j < 8; ++j) {
- if (x + dx[j] > 0 && x + dx[j] <= n && y + dy[j] > 0 && y + dy[j] <= n &&
- gcd(x + dx[j], y + dy[j]) == 1) {
- dfs(num[{x + dx[j], y + dy[j]}]);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n;
- dx.resize(8);
- dx[0] = -2;
- dx[1] = -2;
- dx[2] = -1;
- dx[3] = -1;
- dx[4] = 1;
- dx[5] = 1;
- dx[6] = 2;
- dx[7] = 2;
- dy.resize(8);
- dy[0] = -1;
- dy[1] = 1;
- dy[2] = -2;
- dy[3] = 2;
- dy[4] = -2;
- dy[5] = 2;
- dy[6] = -1;
- dy[7] = 1;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= n; ++j) {
- int x = i / gcd(i, j),
- y = j / gcd(i, j);
- if (num.find({ x, y }) == num.end()) {
- d.push_back({ x, y });
- num[{x, y}] = (int)d.size() - 1;
- }
- }
- }
- sz = (int)d.size();
- used.resize(sz, false);
- check(0);
- for (int i = 0; i < sz; ++i) {
- if (!used[i]) {
- cout << -1;
- return 0;
- }
- }
- fill(used.begin(), used.end(), false);
- dfs(0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement