#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;
scanf("%d %d %d %d", &t, &n, &k1, &k2);
queue <int> Q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &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;
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++) {
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
Compilation message
monetos.cpp: In function 'int main()':
monetos.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
57 | scanf("%d %d %d %d", &t, &n, &k1, &k2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:61:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | scanf("%d", &a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
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 |
2091 ms |
2300 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2084 ms |
2176 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2084 ms |
2300 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2033 ms |
2176 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2090 ms |
2176 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2089 ms |
2168 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2040 ms |
2368 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2091 ms |
2176 KB |
Time limit exceeded |
