| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38911 |
2018-01-07T19:19:22 Z |
qoo2p5 |
Robots (APIO13_robots) |
C++14 |
|
1500 ms |
124592 KB |
#pragma GCC optimize("Ofast,unroll-loops,unroll-all-loops")
#pragma GCC target("sse4,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;
#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)
ll power(ll x, ll y, ll mod = MOD) {
if (y == 0) {
return 1;
}
if (y & 1) {
return power(x, y - 1, mod) * x % mod;
} else {
ll tmp = power(x, y / 2, mod);
return tmp * tmp % mod;
}
}
template<typename A, typename B> bool mini(A &x, const B &y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template<typename A, typename B> bool maxi(A &x, const B &y) {
if (y > x) {
x = y;
return true;
}
return false;
}
void add(ll &x, ll y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
}
ll mult(ll x, ll y) {
return x * y % MOD;
}
void run();
#define TASK ""
int main() {
#ifdef LOCAL
if (strlen(TASK) > 0) {
cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
}
#endif
#ifndef LOCAL
if (strlen(TASK)) {
freopen(TASK ".in", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
cout << fixed << setprecision(12);
run();
return 0;
}
// == SOLUTION == //
const int N = 10;
const int W = 505;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
int n, w, h;
int dp[N][N][W][W];
string f[W];
pair<pair<int, int>, int> step[W][W][4];
pair<int, int> nxt[W][W][4];
bool used[W][W];
bool can_go(int x, int y) {
return 0 <= x && x < h && 0 <= y && y < w && f[x][y] != 'x';
}
void dfs(int x, int y, int dir) {
if (nxt[x][y][dir].first != -3) {
return;
}
if (step[x][y][dir].first.first == -1) {
nxt[x][y][dir] = {x, y};
return;
}
nxt[x][y][dir] = {-2, -2};
int tx = step[x][y][dir].first.first;
int ty = step[x][y][dir].first.second;
int tdir = step[x][y][dir].second;
if (nxt[tx][ty][tdir].first == -2) {
nxt[x][y][dir] = {-1, -1};
return;
}
dfs(tx, ty, tdir);
if (nxt[tx][ty][tdir].first == -1) {
nxt[x][y][dir] = {-1, -1};
return;
}
nxt[x][y][dir] = nxt[tx][ty][tdir];
}
void run() {
cin >> n >> w >> h;
rep(i, 0, N) {
rep(j, 0, N) {
rep(t, 0, W) {
rep(k, 0, W) {
dp[i][j][t][k] = INF;
}
}
}
}
rep(i, 0, h) {
cin >> f[i];
rep(j, 0, w) {
if ('1' <= f[i][j] && f[i][j] <= '9') {
int id = f[i][j] - '1';
dp[id][id + 1][i][j] = 0;
}
}
}
rep(i, 0, h) {
rep(j, 0, w) {
rep(dir, 0, 4) {
int tdir = dir;
if (f[i][j] == 'A') {
tdir = (tdir + 1) % 4;
} else if (f[i][j] == 'C') {
tdir = (tdir + 3) % 4;
}
int nx = i + dx[tdir];
int ny = j + dy[tdir];
if (!can_go(nx, ny)) {
step[i][j][dir] = {{-1, -1}, -1};
} else {
step[i][j][dir] = {{nx, ny}, tdir};
}
nxt[i][j][dir] = {-3, -3};
}
}
}
rep(i, 0, h) {
rep(j, 0, w) {
rep(dir, 0, 4) {
dfs(i, j, dir);
}
}
}
priority_queue<pair<int, pair<int, int>>> q;
rep(len, 1, n + 1) {
rep(l, 0, n - len + 1) {
int r = l + len;
rep(k, l + 1, r) {
rep(x, 0, h) {
rep(y, 0, w) {
mini(dp[l][r][x][y], dp[l][k][x][y] + dp[k][r][x][y]);
}
}
}
memset(used, 0, sizeof used);
rep(x, 0, h) {
rep(y, 0, w) {
if (dp[l][r][x][y] != INF) {
q.push({-dp[l][r][x][y], {x, y}});
}
}
}
while (!q.empty()) {
auto it = q.top();
q.pop();
int x = it.second.first;
int y = it.second.second;
if (used[x][y]) {
continue;
}
used[x][y] = 1;
rep(dir, 0, 4) {
int nx = nxt[x][y][dir].first;
int ny = nxt[x][y][dir].second;
if (nx != -1 && mini(dp[l][r][nx][ny], dp[l][r][x][y] + 1)) {
q.push({-dp[l][r][nx][ny], {nx, ny}});
}
}
}
}
}
int ans = INF;
rep(i, 0, h) {
rep(j, 0, w) {
mini(ans, dp[0][n][i][j]);
}
}
cout << (ans == INF ? -1 : ans) << "\n";
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:74:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".in", "r", stdin);
^
robots.cpp:75:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".out", "w", stdout);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 3 |
Correct |
26 ms |
121992 KB |
Output is correct |
| 4 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 5 |
Correct |
13 ms |
121992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 3 |
Correct |
26 ms |
121992 KB |
Output is correct |
| 4 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 5 |
Correct |
13 ms |
121992 KB |
Output is correct |
| 6 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 9 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
121992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 3 |
Correct |
26 ms |
121992 KB |
Output is correct |
| 4 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 5 |
Correct |
13 ms |
121992 KB |
Output is correct |
| 6 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 9 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 11 |
Correct |
149 ms |
122704 KB |
Output is correct |
| 12 |
Correct |
19 ms |
121992 KB |
Output is correct |
| 13 |
Correct |
29 ms |
122124 KB |
Output is correct |
| 14 |
Correct |
696 ms |
123280 KB |
Output is correct |
| 15 |
Correct |
93 ms |
122508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 3 |
Correct |
26 ms |
121992 KB |
Output is correct |
| 4 |
Correct |
6 ms |
121992 KB |
Output is correct |
| 5 |
Correct |
13 ms |
121992 KB |
Output is correct |
| 6 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 9 |
Correct |
9 ms |
121992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
121992 KB |
Output is correct |
| 11 |
Correct |
149 ms |
122704 KB |
Output is correct |
| 12 |
Correct |
19 ms |
121992 KB |
Output is correct |
| 13 |
Correct |
29 ms |
122124 KB |
Output is correct |
| 14 |
Correct |
696 ms |
123280 KB |
Output is correct |
| 15 |
Correct |
93 ms |
122508 KB |
Output is correct |
| 16 |
Correct |
113 ms |
122256 KB |
Output is correct |
| 17 |
Execution timed out |
1500 ms |
124592 KB |
Execution timed out |
| 18 |
Halted |
0 ms |
0 KB |
- |
