oj.uz

Submission #38958

# Submission time Handle Problem Language Result Execution time Memory
38958 2018-01-08T12:01:44 Z qoo2p5 Robots (APIO13_robots) C++14
100 / 100
 1429 ms 136652 KB 
#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 = 501;
const int T = N * W * W;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int n, w, h;
int dp[N * (N + 1) / 2][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];
vector<int> q[T];
int numb[N][N];

bool can_go(int x, int y) {
	return 0 <= x && x < h && 0 <= y && y < w && f[x][y] != 'x';
}

pair<int, int> get(int x) {
	return {x >> 16, x & ((1 << 16) - 1)};
}

int get(int x, int y) {
	return (x << 16) | y;
}

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;
	{
		int ptr = 0;
		rep(l, 0, n) {
			rep(r, l + 1, n + 1) {
				numb[l][r] = ptr++;
			}
		}
	}
	
	rep(i, 0, N * (N + 1) / 2) {
		rep(t, 0, W) {
			rep(k, 0, W) {
				dp[i][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[numb[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);
			}
		}
	}
		
	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[numb[l][r]][x][y], dp[numb[l][k]][x][y] + dp[numb[k][r]][x][y]);
					}
				}
			}
			
			memset(used, 0, sizeof used);
			rep(x, 0, h) {
				rep(y, 0, w) {
					if (dp[numb[l][r]][x][y] != INF) {
						q[dp[numb[l][r]][x][y]].pb(get(x, y));
					}
				}
			}
			
			rep(t, 0, T) {
				while (sz(q[t])) {
					auto it = get(q[t].back());
					int x = it.first;
					int y = it.second;
					q[t].pop_back();
					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[numb[l][r]][nx][ny], dp[numb[l][r]][x][y] + 1)) {
							q[dp[numb[l][r]][nx][ny]].pb(get(nx, ny));
						}
					}
				}
				q[t].shrink_to_fit();
			}
		}
	}
	
	int ans = INF;
	rep(i, 0, h) {
		rep(j, 0, w) {
			mini(ans, dp[numb[0][n]][i][j]);
		}
	}
	cout << (ans == INF ? -1 : ans) << "\n";
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:72: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:73: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);
                                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 134804 KB Output is correct
2 Correct 56 ms 134804 KB Output is correct
3 Correct 59 ms 134804 KB Output is correct
4 Correct 66 ms 134804 KB Output is correct
5 Correct 63 ms 134804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 134804 KB Output is correct
2 Correct 56 ms 134804 KB Output is correct
3 Correct 59 ms 134804 KB Output is correct
4 Correct 66 ms 134804 KB Output is correct
5 Correct 63 ms 134804 KB Output is correct
6 Correct 66 ms 134804 KB Output is correct
7 Correct 56 ms 134804 KB Output is correct
8 Correct 86 ms 134804 KB Output is correct
9 Correct 76 ms 134804 KB Output is correct
10 Correct 63 ms 134804 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 134804 KB Output is correct
2 Correct 56 ms 134804 KB Output is correct
3 Correct 59 ms 134804 KB Output is correct
4 Correct 66 ms 134804 KB Output is correct
5 Correct 63 ms 134804 KB Output is correct
6 Correct 66 ms 134804 KB Output is correct
7 Correct 56 ms 134804 KB Output is correct
8 Correct 86 ms 134804 KB Output is correct
9 Correct 76 ms 134804 KB Output is correct
10 Correct 63 ms 134804 KB Output is correct
11 Correct 683 ms 135328 KB Output is correct
12 Correct 39 ms 134804 KB Output is correct
13 Correct 376 ms 134936 KB Output is correct
14 Correct 866 ms 135332 KB Output is correct
15 Correct 639 ms 135236 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 134804 KB Output is correct
2 Correct 56 ms 134804 KB Output is correct
3 Correct 59 ms 134804 KB Output is correct
4 Correct 66 ms 134804 KB Output is correct
5 Correct 63 ms 134804 KB Output is correct
6 Correct 66 ms 134804 KB Output is correct
7 Correct 56 ms 134804 KB Output is correct
8 Correct 86 ms 134804 KB Output is correct
9 Correct 76 ms 134804 KB Output is correct
10 Correct 63 ms 134804 KB Output is correct
11 Correct 683 ms 135328 KB Output is correct
12 Correct 39 ms 134804 KB Output is correct
13 Correct 376 ms 134936 KB Output is correct
14 Correct 866 ms 135332 KB Output is correct
15 Correct 639 ms 135236 KB Output is correct
16 Correct 699 ms 135068 KB Output is correct
17 Correct 1429 ms 136652 KB Output is correct
18 Correct 733 ms 136152 KB Output is correct
19 Correct 663 ms 135068 KB Output is correct
20 Correct 1026 ms 136516 KB Output is correct