Shiam7777777

Untitled

Apr 12th, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <cstdio>
  2. #include <numeric>
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <cstring>
  7. #include <string>
  8. #include <map>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <algorithm>
  12. #include <bitset>
  13. #include <queue>
  14. #include <sstream>
  15. #include <deque>
  16. #include <cassert>
  17.  
  18. using namespace std;
  19.  
  20. #define mp make_pair
  21. #define pb push_back
  22. #define rep(i,n) for(int i = 0; i < (n); i++)
  23. #define re return
  24. #define fi first
  25. #define se second
  26. #define sz(x) ((int) (x).size())
  27. #define all(x) (x).begin(), (x).end()
  28. #define sqr(x) ((x) * (x))
  29. #define sqrt(x) sqrt(abs(x))
  30. #define y0 y3487465
  31. #define y1 y8687969
  32. #define fill(x,y) memset(x,y,sizeof(x))
  33. #define prev PREV
  34.                          
  35. typedef vector<int> vi;
  36. typedef long long ll;
  37. typedef long double ld;
  38. typedef double D;
  39. typedef pair<int, int> ii;
  40. typedef vector<ii> vii;
  41. typedef vector<string> vs;
  42. typedef vector<vi> vvi;
  43.  
  44. template<class T> T abs(T x) { re x > 0 ? x : -x; }
  45.  
  46. int n;
  47. int m;
  48. string s[110];
  49. int g[110][110];
  50. int sn;
  51. int sm;
  52.  
  53. int main () {
  54.     int tt;
  55.     cin >> tt;
  56.     for (int it = 1; it <= tt; it++) {
  57.         cin >> n >> m >> sn >> sm;
  58.         for (int i = 0; i < n; i++) cin >> s[i];
  59.         memset (g, 0, sizeof (g));
  60.         for (int i = n - 1; i >= 0; i--)
  61.             for (int j = m - 1; j >= 0; j--)
  62.                 g[i][j] = g[i + 1][j] + g[i][j + 1] - g[i + 1][j + 1] + int (s[i][j] == '@');
  63.         vi wi, wj;
  64.         for (int i = 0; i < n; i++)
  65.             for (int j = 0; j < m; j++)
  66.                 if (s[i][j] == '@') {
  67.                     wi.pb (i);
  68.                     wj.pb (j);
  69.                 }
  70.         sort (all (wi));
  71.         sort (all (wj));
  72.         int cnt = (sn + 1) * (sm + 1);
  73.         int ok = 1;
  74.         if (sz (wi) != 0) {
  75.             if (sz (wi) % cnt != 0) ok = 0; else {
  76.                 vi ri, rj;
  77.                 int di = sz (wi) / (sn + 1);
  78.                 ri.pb (0);
  79.                 for (int i = 0; i < sn; i++)
  80.                     if (wi[di * (i + 1) - 1] == wi[di * (i + 1)]) {
  81.                         ok = 0;
  82.                         break;
  83.                     } else ri.pb (wi[di * (i + 1) - 1] + 1);
  84.                 ri.pb (n);
  85.                 int dj = sz (wj) / (sm + 1);
  86.                 rj.pb (0);
  87.                 for (int i = 0; i < sm; i++)
  88.                     if (wj[dj * (i + 1) - 1] == wj[dj * (i + 1)]) {
  89.                         ok = 0;
  90.                         break;
  91.                     } else rj.pb (wj[dj * (i + 1) - 1] + 1);
  92.                 rj.pb (m);
  93.                 int one = sz (wi) / cnt;
  94.                 for (int i = 0; i < sn + 1 && ok; i++)
  95.                     for (int j = 0; j < sm + 1 && ok; j++) {
  96.                         int cur = g[ri[i]][rj[j]] - g[ri[i + 1]][rj[j]] - g[ri[i]][rj[j + 1]] + g[ri[i + 1]][rj[j + 1]];
  97. //                      cout << ri[i] << " " << rj[j] << " " << ri[i + 1] << " " << rj[j + 1] << endl;
  98. //                      cout << cur << " " << g[ri[i + 1]][rj[j]] << endl;
  99.                         if (cur != one) {
  100.                             ok = 0;
  101.                             break;
  102.                         }
  103.                     }
  104.             }
  105.         }
  106.         cout.precision (20);
  107.         cout << "Case #" << it << ": " << (ok ? "POSSIBLE" : "IMPOSSIBLE");
  108.         cout << endl;
  109.         fprintf (stderr, "%d / %d = %.2f | %.2f\n", it, tt, (double)clock () / CLOCKS_PER_SEC, ((double)clock () / it * tt) / CLOCKS_PER_SEC);
  110.     }
  111.     return 0;
  112. }
Add Comment
Please, Sign In to add comment