Submission #299078

#	Time	Username	Problem	Language	Result	Execution time	Memory
299078		Bruteforceman	Coins (LMIO19_monetos)	C++11	10 / 100	2089 ms	2620 KiB

monetos

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305 + 10;
int a[maxn][maxn], b[maxn][maxn];
int d[maxn][maxn];
pair <int, int> par[maxn][maxn];
int n;
bool inside(int x, int y) {
  return (0 <= x && x < n) && (0 <= y && y < n);
}
bool check(int x, int y) {
  if(not inside(x, y)) return false;
  if(inside(x + 1, y) && b[x + 1][y] == 0) return false;
  if(inside(x, y + 1) && b[x][y + 1] == 0) return false;
  return true;
}
pair <int, int> getOpt(vector <pair <int, int>> can) {
  queue <pair <int, int>> Q;
  for(auto i : can) {
    Q.push(i);
    d[i.first][i.second] = 0;
    par[i.first][i.second] = i;
  }
  vector <pair <int, int>> filled;
  pair <int, int> ret (-1, -1);
  pair <int, int> from (-1, -1);
  bool found = false;
  while(not Q.empty()) {
    int x = Q.front().first;
    int y = Q.front().second;
    int dist = d[x][y];
    d[x][y] = -1;
    Q.pop();
    if(not found) {
      if(a[x][y] == 1) {
        found = true;
        ret = make_pair(x, y);
        from = par[x][y];
      }
    }
    if(found) continue;
    if(inside(x - 1, y) && d[x - 1][y] == -1) {
      d[x - 1][y] = 1 + dist;
      par[x - 1][y] = par[x][y];
      Q.emplace(x - 1, y);
    }
    if(inside(x, y - 1) && d[x][y - 1] == -1) {
      d[x][y - 1] = 1 + dist;
      par[x][y - 1] = par[x][y];
      Q.emplace(x, y - 1);
    }
  }
  return ret;
}
int main() {
  int t, k1, k2;
  cin >> t >> n >> k1 >> k2;
  queue <int> Q;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }
  memset(d, -1, sizeof d);
  vector <pair <int, int>> can;
  can.emplace_back(n - 1, n - 1);
  while(true) {
    auto x = getOpt(can);
    if(x == make_pair(-1, -1)) break;
    auto y = par[x.first][x.second];
    can.erase(find(can.begin(), can.end(), y));
    a[x.first][x.second] = 0;
    b[y.first][y.second] = 1;
    // cout << x.first << " " << x.second << endl;
    // cout << y.first << " " << y.second << endl;
    
    if(check(y.first - 1, y.second)) {
      can.emplace_back(y.first - 1, y.second);
    }
    if(check(y.first, y.second - 1)) {
      can.emplace_back(y.first, y.second - 1);
    }
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cout << b[i][j] << " \n"[j == n - 1];
    }
  }
  return 0;
}

• Subtask 1: 10 / 100