Advertisement
toonewbie

Untitled

Apr 12th, 2019
496
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. /****Author: Barish Namazov****/
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. /***TEMPLATE***/
  7. #define all(v) (v).begin(),(v).end()
  8. #define rall(v) (v).rbegin(),(v).rend()
  9.  
  10. #define F first
  11. #define S second
  12. #define pb push_back
  13.  
  14. #define endl '\n'
  15.  
  16. const int max4 = 10004;
  17. const int maxx = 200005;
  18. const int max6 = 1000006;
  19. const int lg5 = 17;
  20.  
  21. const int INF = 1000000007;
  22. const long long INFLL = 4LL * 1000000000 * 1000000000;
  23.  
  24. /***************/
  25.  
  26. int powmod (int a, int b, int mod) {
  27.     int res = 1; a %= mod;
  28.     for (; b; b >>= 1) {
  29.         if (b & 1) {
  30.             res = 1LL * res * a % mod;
  31.         }
  32.         a = 1LL * a * a % mod;
  33.     }
  34.     return res;
  35. }
  36.  
  37. int gcd (int a, int b) {
  38.     while (b > 0) {
  39.         int t = a % b;
  40.         a = b, b = t;
  41.     }
  42.     return a;
  43. }
  44.  
  45. int lcm (int a, int b) {
  46.     return (a / gcd (a, b)) * b;
  47. }
  48.  
  49. int is_prime (int n) {
  50.     if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
  51.         return 0;
  52.     for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
  53.         if (n % i == 0)
  54.             return 0;
  55.     return 1;
  56. }
  57.  
  58. /******Don't forget to use long long when needed!!******/
  59.  
  60. int n, m;
  61. vector <pair <int, int>> lol, emp;
  62. vector <vector <int>> loll;
  63. vector <pair <int, int>> go(int i, int j, int cnt, vector <pair <int, int>> v, vector <vector <int>> used) {
  64.     v.pb({i, j});
  65.     used[i][j] = 1;
  66.     if (cnt == n * m) {
  67.         return v;
  68.     }
  69.     vector <pair <int, pair <int, int>>> soxus;
  70.     for (int ii = 1; ii <= n; ii++) {
  71.         for (int jj = 1; jj <= m; jj++) {
  72.             if (used[ii][jj] == 1 || i == ii || j == jj || i - j == ii - jj || i + j == ii + jj) continue;
  73.             soxus.pb({abs(i - ii) + abs(j - jj), {ii, jj}});/*
  74.             auto cur = go(ii, jj, cnt + 1, v, used);
  75.             if (cur.size() > 0) {
  76.                 return cur;
  77.             }*/
  78.         }
  79.     }
  80.     if (soxus.size() > 0) {
  81.         sort(all(soxus));
  82.         auto x = soxus[0], y = soxus.back(); swap(x, y);
  83.         auto cur1 = go(x.S.F, x.S.S, cnt + 1, v, used);
  84.         if (cur1.size() > 0) return cur1;
  85.         auto cur2 = go(y.S.F, y.S.S, cnt + 1, v, used);
  86.         return cur2;
  87.     }
  88.     return emp;
  89. }
  90. int main() {
  91.     //freopen("sleepy.in","r",stdin);
  92.     //freopen("sleepy.out","w",stdout);
  93.     ios_base :: sync_with_stdio(0);
  94.     cin.tie(0), cout.tie(0);
  95.     int T;
  96.     cin >> T;
  97.     for (int cs = 1; cs <= T; cs++) {
  98.         cin >> n >> m;
  99.         vector <pair <int, int>> res;
  100.         loll = vector <vector <int>>(n + 1, vector <int>(m + 1));
  101.         for (int i = 1;  i <= n; i++) {
  102.             for (int j = 1; j <= m; j++) {
  103.                 auto cur = go(i, j, 1, lol, loll);
  104.                 if (cur.size() > 0) {
  105.                     res = cur;
  106.                     break;
  107.                 }
  108.             }
  109.             if (res.size() > 0) break;
  110.         }
  111.         cout << "Case #" << cs << ": ";
  112.         if (res.size() == 0) {
  113.             cout << "IMPOSSIBLE" << endl;
  114.         } else {
  115.             cout << "POSSIBLE" << endl;
  116.             for (auto x : res) {
  117.                 cout << x.F << " " << x.S << endl;
  118.             }
  119.         }
  120.     }
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement