Advertisement
Guest User

Untitled

a guest
Apr 8th, 2019
248
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.91 KB | None | 0 0
  1. #include <vector>
  2. #include <sstream>
  3. #include <algorithm>
  4. #include <fstream>
  5. #include <list>
  6. #include <unordered_map>
  7. #include <map>
  8. #include <istream>
  9. #include <sstream>
  10. #include <stack>
  11. #include <ctime>
  12. #include <stdio.h>
  13. #include <set>
  14. #include <cmath>
  15. #include <bitset>
  16. #include <iostream>
  17. #include <iomanip>
  18. #include <queue>
  19. #include <string>
  20.  
  21. #define endl "\n"
  22. /*#define all(x) x.begin(),x.end()
  23. #define rr return 0
  24. #define xx first
  25. #define yy second
  26. #define pii pair<int,int>
  27. #define lcm(a,b) a*b/gcd(a,b)*/
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33.  
  34.  
  35. signed main(){
  36. ios_base::sync_with_stdio(false);
  37. cin.tie(0);
  38. cout.tie(0);
  39. int t;
  40. int r, c, h, v;
  41. cin >> t;
  42. int pp = 1;
  43. vector<vector<char>> a;
  44. vector<int> rows;
  45. vector<int> cols;
  46. while(t){
  47. cin >> r >> c >> h >> v;
  48. a.resize(r);
  49. rows.resize(r);
  50. cols.resize(c);
  51. string s;
  52. int ch = 0;
  53. for(int i = 0;i < r;i++){
  54. a[i].resize(c);
  55. cin >> s;
  56. for(int j = 0;j < c;j++){
  57. a[i][j] = s[j];
  58. if(a[i][j] == '@'){
  59. ch++;
  60. }
  61. }
  62. }
  63. int num = (h + 1) * (v + 1);
  64. if(ch == 0){
  65. cout << "Case #" << pp << ": ";
  66. pp++;
  67. cout << "POSSIBLE" << endl;
  68. continue;
  69. }
  70. int numc, numr;
  71. numc = ch / (v + 1);
  72. numr = ch / (h + 1);
  73. bool ok = true;
  74. if(ch % num != 0){
  75. ok = 0;
  76. }
  77. int inone = ch / num;
  78. for(int i = 0;i < r;i++){
  79. int u = 0;
  80. for(int j = 0;j < c;j++){
  81. if(a[i][j] == '@'){
  82. u++;
  83. }
  84. }
  85. rows[i] = u;
  86. }
  87. for(int i = 0;i < c;i++){
  88. int u = 0;
  89. for(int j = 0;j < r;j++){
  90. if(a[j][i] == '@'){
  91. u++;
  92. }
  93. }
  94. cols[i] = u;
  95. }
  96. int tmp = 0;
  97. int cs = 0;
  98. vector<int> colR;
  99. for(int i = 0;i < c;i++){
  100. tmp += cols[i];
  101. if(tmp > numc){
  102. ok = 0;
  103. }else if(tmp == numc){
  104. tmp = 0;
  105. cs++;
  106. if((i + 1) >= 0 && (i + 1) < c)
  107. colR.push_back(i + 1);
  108. }else if(i == c-1 && tmp < numc){
  109. ok = 0;
  110. }
  111. }
  112. colR.push_back(c);
  113. int rs = 0;
  114. int prevRaz = 0;
  115. tmp = 0;
  116. for(int i = 0;i < r;i++){
  117. tmp += rows[i];
  118. if(tmp > numr){
  119. ok = 0;
  120. }else if(tmp == numr){
  121. int ch1 = 0;
  122. int prev = 0;
  123. for(int j : colR){
  124. ch1 = 0;
  125. for(int z = prevRaz;z <= i;z++){
  126. for(int k = prev;k < j;k++){
  127. if(a[z][k] == '@'){
  128. ch1++;
  129. }
  130. }
  131. }
  132. prev = j;
  133. if(ch1 != inone){
  134. ok = 0;
  135. break;
  136. }
  137. }
  138. if(!ok){
  139. break;
  140. }
  141. tmp = 0;
  142. rs++;
  143. prevRaz = i + 1;
  144. }else if(i == r-1 && tmp < numr){
  145. ok = 0;
  146. }
  147. }
  148. if(cs != (v + 1) && rs != (h + 1)){
  149. ok = 0;
  150. }
  151. cout << "Case #" << pp << ": ";
  152. if(ok)
  153. cout << "POSSIBLE" << endl;
  154. else
  155. cout << "IMPOSSIBLE" << endl;
  156. --t;
  157. pp++;
  158. colR.clear();
  159. }
  160. return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement