Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int dx[4] = {-1, 0, 0, 1};
- int dy[4] = {0, -1, 1, 0};
- int res = 0;
- pair <int, int> ffind(pair <int, int> x){
- while (dsu[x.f][x.s] != x){
- x = dsu[x.f][x.s];
- }
- return x;
- }
- void uunion(pair <int, int> x, pair <int, int> y){
- x = ffind(x);
- y = ffind(y);
- if (h[x.f][x.s] > h[y.f][y.s]){
- dsu[y.f][y.s] = x;
- cnt[x.f][x.s] += cnt[y.f][y.s];
- }
- else{
- dsu[x.f][x.s] = y;
- cnt[y.f][y.s] += cnt[x.f][x.s];
- if (h[x.f][x.s] == h[y.f][y.s]){
- h[y.f][y.s]++;
- }
- }
- }
- void dfs(int x, int y, int val){
- if (res == 0){
- return;
- }
- used[x][y] = val;
- res--;
- for (int i = 0; i < 4; i++){
- int tox = x + dx[i];
- int toy = y + dy[i];
- if (check(tox, toy) && !used[tox][toy]
- && a[tox][toy] >= val && res > 0){
- dfs(tox, toy, val);
- }
- }
- }
- int main(){
- int n;
- cin >> n >> m >> k;
- vector <pair <int, pair <int, int> > > vec;
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- cin >> a[i][j];
- dsu[i][j] = {i, j};
- h[i][j] = 1;
- cnt[i][j] = 1;
- was[i][j] = 0;
- vec.pb({a[i][j], {i, j}});
- }
- }
- sort(vec.begin(), vec.end());
- reverse(vec.begin(), vec.end());
- for (int i = 0; i < vec.size(); i++){
- int val = vec[i].f;
- int x = vec[i].s.f;
- int y = vec[i].s.s;
- was[x][y] = 1;
- for (int j = 0; j < 4; j++){
- int tox = x + dx[j];
- int toy = y + dy[j];
- if (check(tox, toy) && was[tox][toy]){
- uunion(make_pair(x, y), make_pair(tox, toy));
- }
- }
- if (k % val == 0){
- pair <int, int> z = ffind(make_pair(x, y));
- if (cnt[z.f][z.s] * val >= k){
- ansx = x;
- ansy = y;
- break;
- }
- }
- }
- res = k / a[ansx][ansy];
- dfs(ansx, ansy, a[ansx][ansy]);
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- cout << used[i][j] << ' ';
- }
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment