oj.uz

Submission #758799

# Submission time Handle Problem Language Result Execution time Memory
758799 2023-06-15T10:19:19 Z fanwen Robots (APIO13_robots) C++17
100 / 100
 330 ms 146888 KB 
/**
 *      author : pham van sam 
 *      created : 15 June 2023 (Thursday)
 **/

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 505, INF = MAXN * MAXN;
const int dir[] = {-1, 0, 1, 0, 0, 1, 0, -1};


int N, Row, Col, dp[10][10][MAXN][MAXN];
string a[MAXN];
pair <int, int> nxt[MAXN][MAXN][4];
vector <pair <int, int>> q[INF];

bool inside(int x, int y) {
    return x >= 0 && x < Row && y >= 0 && y < Col;
}

pair <int, int> end_point(int x, int y, int d) {
    pair <int, int> &cur = nxt[x][y][d];
    if(cur.first != -1) return cur;
    int u = x + dir[d], v = y + dir[d + 4];
    if(!inside(u, v)) return cur = make_pair(x, y);
    if(a[u][v] == 'x') return cur = make_pair(x, y);

    if(a[u][v] == 'A') d = (d + 3) % 4;
    if(a[u][v] == 'C') d = (d + 1) % 4;
    
    return cur = end_point(u, v, d);
}

void process(void) {
    cin >> N >> Col >> Row;
    REP(i, Row) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);

    REP(i, Row) REP(j, Col) if(a[i][j] >= '1' && a[i][j] <= '9') {
        dp[a[i][j] - '0' - 1][a[i][j] - '0' - 1][i][j] = 0;
    }
    REP(i, Row) REP(j, Col) REP(d, 4) {
        nxt[i][j][d] = make_pair(-1, -1);
    }

    REP(rng, N) {
        FOR(l, 0, N - rng - 1) {
            int r = l + rng;
            FOR(t, l, r - 1) REP(i, Row) REP(j, Col) if(a[i][j] != 'x') {
                minimize(dp[l][r][i][j], dp[l][t][i][j] + dp[t + 1][r][i][j]);
            }
        }
        FOR(l, 0, N - rng - 1) {
            int r = l + rng;
            REP(i, Row) REP(j, Col) if(a[i][j] != 'x') {
                if(dp[l][r][i][j] < INF) q[dp[l][r][i][j]].emplace_back(i, j);
            }
            FOR(i, 0, Row * Col) {
                for (auto [x, y] : q[i]) {
                    if(dp[l][r][x][y] != i) continue;
                    REP(d, 4) {
                        auto [nx, ny] = end_point(x, y, d);
                        if(minimize(dp[l][r][nx][ny], dp[l][r][x][y] + 1)) {
                            q[dp[l][r][nx][ny]].emplace_back(nx, ny);
                        }
                    }
                }
                q[i].clear();
            }
        }
    }
    int res = INF;
    REP(i, Row) REP(j, Col) minimize(res, dp[0][N - 1][i][j]);
    // REP(i, Row) REP(j, Col) cout << dp[1][1][i][j] << " \n"[j == Col - 1];
    cout << (res >= INF ? -1 : res) ;
}

signed main() {

    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        process();
        // cout << '\n';
    }

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106088 KB Output is correct
2 Correct 37 ms 106104 KB Output is correct
3 Correct 42 ms 106184 KB Output is correct
4 Correct 38 ms 106044 KB Output is correct
5 Correct 38 ms 106072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106088 KB Output is correct
2 Correct 37 ms 106104 KB Output is correct
3 Correct 42 ms 106184 KB Output is correct
4 Correct 38 ms 106044 KB Output is correct
5 Correct 38 ms 106072 KB Output is correct
6 Correct 37 ms 106060 KB Output is correct
7 Correct 45 ms 106120 KB Output is correct
8 Correct 39 ms 106024 KB Output is correct
9 Correct 39 ms 106020 KB Output is correct
10 Correct 39 ms 106080 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106088 KB Output is correct
2 Correct 37 ms 106104 KB Output is correct
3 Correct 42 ms 106184 KB Output is correct
4 Correct 38 ms 106044 KB Output is correct
5 Correct 38 ms 106072 KB Output is correct
6 Correct 37 ms 106060 KB Output is correct
7 Correct 45 ms 106120 KB Output is correct
8 Correct 39 ms 106024 KB Output is correct
9 Correct 39 ms 106020 KB Output is correct
10 Correct 39 ms 106080 KB Output is correct
11 Correct 83 ms 114124 KB Output is correct
12 Correct 42 ms 110736 KB Output is correct
13 Correct 62 ms 110280 KB Output is correct
14 Correct 143 ms 119276 KB Output is correct
15 Correct 75 ms 111448 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106088 KB Output is correct
2 Correct 37 ms 106104 KB Output is correct
3 Correct 42 ms 106184 KB Output is correct
4 Correct 38 ms 106044 KB Output is correct
5 Correct 38 ms 106072 KB Output is correct
6 Correct 37 ms 106060 KB Output is correct
7 Correct 45 ms 106120 KB Output is correct
8 Correct 39 ms 106024 KB Output is correct
9 Correct 39 ms 106020 KB Output is correct
10 Correct 39 ms 106080 KB Output is correct
11 Correct 83 ms 114124 KB Output is correct
12 Correct 42 ms 110736 KB Output is correct
13 Correct 62 ms 110280 KB Output is correct
14 Correct 143 ms 119276 KB Output is correct
15 Correct 75 ms 111448 KB Output is correct
16 Correct 109 ms 114572 KB Output is correct
17 Correct 330 ms 146888 KB Output is correct
18 Correct 137 ms 118668 KB Output is correct
19 Correct 102 ms 114648 KB Output is correct
20 Correct 192 ms 129456 KB Output is correct