YEZAELP

JAM: Waffle Choppers

Jun 19th, 2021
693
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e2;
  5. int qs[N+10][N+10];
  6. vector <int> Col;
  7. int n, m;
  8.  
  9. bool check(int part, int block){
  10.     int previ = 0, cnt = 0;
  11.     for(int i=1;i<=n;i++){
  12.         int prevj = 0;
  13.         bool ch = true;
  14.         for(auto j: Col){
  15.             int sum = qs[i][j] - qs[i][prevj] - qs[previ][j] + qs[previ][prevj];
  16.             if(sum != block){
  17.                 ch = false;
  18.                 break;
  19.             }
  20.             prevj = j;
  21.         }
  22.         if(!ch) continue;
  23.         cnt += Col.size();
  24.         previ = i;
  25.     }
  26.     return cnt == part;
  27. }
  28.  
  29. bool f(){
  30.     scanf("%d%d", &n, &m);
  31.     int h, v;
  32.     scanf("%d%d", &h, &v);
  33.     h ++;
  34.     v ++;
  35.     int part = h * v;
  36.  
  37.     for(int i=1;i<=n;i++){
  38.         for(int j=1;j<=m;j++){
  39.             char ch;
  40.             scanf(" %c", &ch);
  41.             qs[i][j] = qs[i-1][j] + qs[i][j-1] - qs[i-1][j-1] + (ch == '@');
  42.         }
  43.     }
  44.  
  45.     int block = qs[n][m] / part;
  46.  
  47.     int SumCol = block * h;
  48.     int prevj = 0;
  49.     for(int j=1;j<=m;j++){
  50.         if(qs[n][j] - qs[n][prevj] == SumCol) {
  51.             Col.push_back(j);
  52.             prevj = j;
  53.         }
  54.     }
  55.  
  56.     if(qs[n][m] == 0) return true;
  57.     return check(part, block);
  58. }
  59.  
  60. int main(){
  61.  
  62.     int Q;
  63.     scanf("%d", &Q);
  64.  
  65.     for(int q=1;q<=Q;q++){
  66.         if(f()) printf("Case #%d: POSSIBLE", q);
  67.         else printf("Case #%d: IMPOSSIBLE", q);
  68.         printf("\n");
  69.         if(!Col.empty()) Col.clear();
  70.     }
  71.  
  72.  
  73.     return 0;
  74. }
  75.  
RAW Paste Data