Submission #299078

# Submission time Handle Problem Language Result Execution time Memory
299078 2020-09-14T13:03:25 Z Bruteforceman Coins (LMIO19_monetos) C++11
10 / 100
2000 ms 2620 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB K = 17
2 Incorrect 7 ms 1024 KB K = 594
3 Execution timed out 2088 ms 2424 KB Time limit exceeded
4 Execution timed out 2071 ms 2304 KB Time limit exceeded
5 Execution timed out 2086 ms 2304 KB Time limit exceeded
6 Execution timed out 2087 ms 2296 KB Time limit exceeded
7 Execution timed out 2084 ms 2296 KB Time limit exceeded
8 Execution timed out 2087 ms 2424 KB Time limit exceeded
9 Execution timed out 2078 ms 2620 KB Time limit exceeded
10 Execution timed out 2089 ms 2424 KB Time limit exceeded