oj.uz

Submission #248403

# Submission time Handle Problem Language Result Execution time Memory
248403 2020-07-12T11:16:17 Z receed Robots (APIO13_robots) C++14
100 / 100
 556 ms 51724 KB 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 501, INF = 1e9;
char a[N][N];
int to[N * N][4], tr[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}, used[N * N];
int d[9][9][N * N];
int n, w, h;

int getn(int x, int y) {
    return x * w + y;
}

int go(int x, int y, int dr) {
    if (x < 0 || x >= h || y < 0 || y >= w || a[x][y] == 'x')
        return getn(x - tr[dr][0], y - tr[dr][1]);
    int num = getn(x, y);
    if (to[num][dr] != -1)
        return to[num][dr];
    to[num][dr] = -2;
    int nd = dr;
    if (a[x][y] == 'A')
        nd = (dr + 1) % 4;
    else if (a[x][y] == 'C')
        nd = (dr + 3) % 4;
    x += tr[nd][0];
    y += tr[nd][1];
    to[num][dr] = go(x, y, nd);
    return to[num][dr];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> w >> h;
    rep(i, h)
        cin >> a[i];
    rep(i, w * h)
        rep(j, 4)
            to[i][j] = -1;
    rep(i, h)
        rep(j, w)
            if (a[i][j] != 'x')
                rep(k, 4)
                    go(i, j, k);
    int v;
    for (int l = n - 1; l >= 0; l--)
        for (int r = l; r < n; r++) {
            vector<pair<int, int>> li;
            rep(i, h * w) {
                used[i] = 0;
                d[l][r][i] = INF;
                if (l == r && a[i / w][i % w] == '1' + l)
                    d[l][r][i] = 0;
                for (int j = l; j < r; j++)
                    d[l][r][i] = min(d[l][r][i], d[l][j][i] + d[j + 1][r][i]);
                if (d[l][r][i] < INF)
                    li.push_back({d[l][r][i], i});
            }
            queue<int> q;
            sort(rall(li));
            while (!q.empty() || !li.empty()) {
                if (li.empty() || !q.empty() && d[l][r][q.front()] < li.back().first) {
                    v = q.front();
                    q.pop();
                }
                else {
                    v = li.back().second;
                    li.pop_back();
                }
                if (used[v])
                    continue;
                used[v] = 1;
                rep(i, 4)
                    if (to[v][i] >= 0 && d[l][r][to[v][i]] > d[l][r][v] + 1) {
                        d[l][r][to[v][i]] = d[l][r][v] + 1;
                        q.push(to[v][i]);
                    }
            }
        }
    int ans = INF;
    rep(i, h * w)
        ans = min(ans, d[0][n - 1][i]);
    if (ans == INF)
        ans = -1;
    cout << ans;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:86:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if (li.empty() || !q.empty() && d[l][r][q.front()] < li.back().first) {
                                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 69 ms 18344 KB Output is correct
12 Correct 5 ms 2688 KB Output is correct
13 Correct 22 ms 12428 KB Output is correct
14 Correct 197 ms 19064 KB Output is correct
15 Correct 47 ms 18176 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 69 ms 18344 KB Output is correct
12 Correct 5 ms 2688 KB Output is correct
13 Correct 22 ms 12428 KB Output is correct
14 Correct 197 ms 19064 KB Output is correct
15 Correct 47 ms 18176 KB Output is correct
16 Correct 109 ms 50040 KB Output is correct
17 Correct 556 ms 51724 KB Output is correct
18 Correct 129 ms 49656 KB Output is correct
19 Correct 98 ms 49996 KB Output is correct
20 Correct 355 ms 51316 KB Output is correct