Advertisement
Guest User

Untitled

a guest
Jun 3rd, 2018
310
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using pii = pair<int, int>;
  7. using pll = pair<ll, ll>;
  8. using ld = long double;
  9.  
  10. ll get_root(ll n) {
  11.     assert(n >= 0);
  12.     ll x = sqrt(n);
  13.     while (x * x < n)
  14.         x++;
  15.     while (x * x > n)
  16.         x--;
  17.     if (x * x != n)
  18.         return -1;
  19.     return x;
  20. }
  21.  
  22. vector<pii> get_pairs(ll n) {
  23.     vector<pii> ans;
  24.     for (ll a = 0; a * a <= n; a++) {
  25.         ll b = get_root(n - a * a);
  26.         if (b != -1) {
  27.             assert(a * a + b * b == n);
  28.             ans.emplace_back(a, b);
  29.          }
  30.     }
  31.     return ans;
  32. }
  33.  
  34. const int N = 666;
  35.  
  36. bool was[N][N];
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(nullptr);
  41.  
  42.     int n, a, b;
  43.     cin >> n >> a >> b;
  44.  
  45.     auto ps = get_pairs(a);
  46.     for (auto p : get_pairs(b))
  47.         ps.push_back(p);
  48.    
  49.  
  50.     for (int rep = 2;; rep++) {
  51.         vector<pii> cands;
  52.         for (int i = 0; i < 2 * n; i++) {
  53.             for (int j = 0; j < 2 * n; j++) {
  54.                 cands.emplace_back(i, j);
  55.                 was[i][j] = false;
  56.             }
  57.         }
  58.         if (rep <= 7)
  59.             stable_sort(cands.begin(), cands.end(), [rep](auto a, auto b) { return (a.first + a.second) % rep < (b.first + b.second) % rep; });
  60.         else
  61.             stable_sort(cands.begin(), cands.end(), [rep](auto a, auto b) { return abs(a.first - a.second) % (rep - 6) <abs(b.first - b.second) % (rep - 6); });
  62.         vector<pii> ans;
  63.         for (auto p : cands) {
  64.             int i = p.first;
  65.             int j = p.second;
  66.             if (was[i][j] || ans.size() == n * n)
  67.                 continue;
  68.             ans.emplace_back(i, j);
  69.             for (int dx = -1; dx <= 1; dx += 2) {
  70.                 for (int dy = -1; dy <= 1; dy += 2) {
  71.                     for (auto d : ps) {
  72.                         int x = i + d.first * dx;
  73.                         int y = j + d.second * dy;
  74.                         if (x >= 0 && x < 2 * n && y >= 0 && y < 2 * n)
  75.                             was[x][y] = true;
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.         if (ans.size() < n * n) {
  81.             continue;
  82.         }
  83.         for (auto p : ans)
  84.             cout << p.first << " " << p.second << "\n";
  85.         return 0;
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement