Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1000;
- const int MAXS = 355;
- const int MOD = 1e9 + 7;
- struct Cell
- {
- int x1, y1, x2, y2;
- bool operator <(const Cell& other) const
- {
- if (x1 == other.x1)
- {
- if (x2 == other.x2)
- {
- if (y1 == other.y1)
- return y2 < other.y2;
- return y1 < other.y1;
- }
- else
- {
- return x2 < other.x2;
- }
- }
- else
- {
- return x1 < other.x1;
- }
- }
- };
- map<Cell, int>mp;
- char s[MAXS];
- int rep[MAXS];
- int sol[MAXN + 5];
- int a[MAXN + 5][MAXN + 5];
- int m, k, t;
- int mx, my;
- void getRep(int n)
- {
- int nr = 0;
- for (int i = 1; i <= n; ++i)
- {
- if ('0' <= s[i] && s[i] <= '9')
- {
- nr = nr * 10 + s[i] - '0';
- }
- else
- {
- if (nr)
- rep[++m] = nr, nr = 0;
- if (s[i] == 'H')
- rep[++m] = -1;
- else if (s[i] == 'V')
- rep[++m] = -2;
- else
- rep[++m] = -3;
- }
- }
- }
- void Cerinta1(int n)
- {
- int ans = 0;
- for (int i = 1; i <= n; ++i)
- if (s[i] == '*')
- ans++;
- cout<<ans<<'\n';
- }
- void solve(int l, int r)
- {
- mx = max(mx, l);
- my = max(my, r);
- if (rep[k] == -3)
- {
- k++;
- return ;
- }
- if (rep[k] == -1)
- {
- k++;
- int nl = l + rep[k];
- k++;
- solve(l, r);
- solve(nl, r);
- }
- else
- {
- k++;
- int nr = r + rep[k];
- k++;
- solve(l, r);
- solve(l, nr);
- }
- }
- void Cerinta2(int n)
- {
- k = 1;
- solve(1, 1);
- cout<<mx<<" "<<my;
- }
- void Partaj(int x1, int y1, int x2, int y2)
- {
- if (rep[k] == -3)
- {
- k++;
- t++;
- for (int i = x1; i <= x2; ++i)
- for (int j = y1; j <= y2; ++j)
- a[i][j] = t;
- return ;
- }
- if (rep[k] == -1)
- {
- k++;
- int nx = x1 + rep[k];
- k++;
- Partaj(x1, y1, nx - 1, y2);
- Partaj(nx, y1, x2, y2);
- }
- else
- {
- k++;
- int ny = y1 + rep[k];
- k++;
- Partaj(x1, y1, x2, ny - 1);
- Partaj(x1, ny, x2, y2);
- }
- }
- int getw(int x1, int y1, int x2, int y2)
- {
- if (mp.count({x1, y1, x2, y2}))
- return mp[ {x1, y1, x2, y2}];
- int ind = -1, r = 0, okk = 0;
- for (int i = x1; i < x2; ++i)
- {
- bool ok = 1;
- for (int j = y1; j <= y2 && ok; ++j)
- if (a[i][j] == a[i + 1][j])
- ok = 0;
- if (ok && a[i][y2] < a[i + 1][y1])
- {
- ind = i;
- okk = 1;
- r = (r + 1LL * getw(x1, y1, ind, y2) * getw(ind + 1, y1, x2, y2)) % MOD;
- }
- }
- ind = -1;
- for (int j = y1; j < y2; ++j)
- {
- bool ok = 1;
- for (int i = x1; i <= x2 && ok; ++i)
- if (a[i][j] == a[i][j + 1])
- ok = 0;
- if (ok && a[x2][j] < a[x1][j + 1])
- {
- ind = j;
- okk = 1;
- r = (r + 1LL * getw(x1, y1, x2, ind) * getw(x1, ind + 1, x2, y2)) % MOD;
- }
- }
- if (okk == 0)
- r = 1;
- mp[ {x1, y1, x2, y2}] = r;
- return r;
- }
- void Cerinta3(int n)
- {
- k = 1;
- solve(1, 1);
- k = 1;
- Partaj(1, 1, mx, my);
- cout<<getw(1, 1, mx, my)<<'\n';
- }
- void getm(int x1, int y1, int x2, int y2)
- {
- int ind = -1;
- for (int i = x1; i < x2; ++i)
- {
- bool ok = 1;
- for (int j = y1; j <= y2 && ok; ++j)
- if (a[i][j] == a[i + 1][j])
- ok = 0;
- if (ok && a[i][y2] < a[i + 1][y1])
- {
- ind = i;
- break;
- }
- }
- if (ind != -1)
- {
- sol[++k] = -1;
- sol[++k] = ind - x1 + 1;
- getm(x1, y1, ind, y2);
- getm(ind + 1, y1, x2, y2);
- }
- else
- {
- for (int j = y1; j < y2; ++j)
- {
- bool ok = 1;
- for (int i = x1; i <= x2 && ok; ++i)
- if (a[i][j] == a[i][j + 1])
- ok = 0;
- if (ok && a[x2][j] < a[x1][j + 1])
- {
- ind = j;
- break;
- }
- }
- if (ind != -1)
- {
- sol[++k] = -2;
- sol[++k] = ind - y1 + 1;
- getm(x1, y1, x2, ind);
- getm(x1, ind + 1, x2, y2);
- }
- else
- {
- sol[++k] = -3;
- }
- }
- }
- void Cerinta4(int n)
- {
- k = 1;
- solve(1, 1);
- k = 1;
- Partaj(1, 1, mx, my);
- k = 0;
- getm(1, 1, mx, my);
- for (int i = 1; i <= k; ++i)
- if (sol[i] == -1)
- cout<<"H";
- else if (sol[i] == -2)
- cout<<"V";
- else if (sol[i] == -3)
- cout<<"*";
- else
- cout<<sol[i];
- cout<<'\n';
- }
- int main()
- {
- int p;
- cin>>p;
- cin.get();
- cin.getline(s+1, MAXS);
- int len = strlen(s + 1);
- getRep(len);
- if(p == 1)
- Cerinta1(len);
- else if (p == 2)
- Cerinta2(len);
- else if (p == 3)
- Cerinta3(len);
- else
- Cerinta4(len);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement