oj.uz

Submission #969838

# Submission time Handle Problem Language Result Execution time Memory
969838 2024-04-25T16:26:11 Z steveonalex Robots (APIO13_robots) C++17
60 / 100
 826 ms 163840 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

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

const int N = 505, K = 9, INF = 1e9 + 69;

enum GridObj{none=0, obstacle=1, anti_clockwise=2, clockwise=3};

int n, w, h;
int dp[45][N][N];
int dis[N][N][4];
bool visited[N][N][4];

int convert(int l, int r){
    int ans = 0;
    for(int i = 0; i<l; ++i) ans += n - i;
    ans += r - l;
    return ans;
}

GridObj grid[N][N];
pair<int, int> pos[K];

vector<array<int, 3>> q[N * N];

void dijkstra(int l, int r){
    memset(dis, 63, sizeof dis);
    memset(visited, 0, sizeof visited);

    int edging = convert(l, r);
    int cnt = 0;
    if (l < r){
        for(int mid = l; mid < r; ++mid){
            for(int i = 1; i<=w; ++i) for(int j = 1;j <=h; ++j) 
                minimize(dp[edging][i][j], dp[convert(l, mid)][i][j] + dp[convert(mid + 1, r)][i][j]);
        }
    }
    for(int i = 1; i<=w; ++i) for(int j = 1;j <=h; ++j) if (dp[convert(l, r)][i][j] < INF) {
        for(int x = 0; x < 4; ++x){
            dis[i][j][x] = dp[edging][i][j];
            q[dp[edging][i][j]].push_back({{i, j, x}});
            cnt++;
        }
    }

    for(int distance = 0; cnt > 0; ++distance){
        while(q[distance].size()){
            array<int, 3> u = q[distance].back(); q[distance].pop_back();
            cnt--;

            // cout << distance << " "; printArr(u); cout.flush();

            if (visited[u[0]][u[1]][u[2]]) continue;
            visited[u[0]][u[1]][u[2]] = true;
            
            array<int, 3> v = {{u[0] + dx[u[2]], u[1]+ dy[u[2]], u[2]}};
            if (grid[v[0]][v[1]] == anti_clockwise) v[2] = (v[2] + 1) % 4;
            else if (grid[v[0]][v[1]] == clockwise) v[2] = (v[2] + 3) % 4;

            if (grid[v[0]][v[1]] == obstacle){
                minimize(dp[edging][u[0]][u[1]], distance + 1);
                for(int x = 0; x < 4; ++x){
                    array<int, 3> v = {{u[0] + dx[x], u[1] + dy[x], x}};
                    if (grid[v[0]][v[1]] == anti_clockwise) v[2] = (v[2] + 1) % 4;
                    else if (grid[v[0]][v[1]] == clockwise) v[2] = (v[2] + 3) % 4;
                    if (grid[v[0]][v[1]] != obstacle && minimize(dis[v[0]][v[1]][v[2]], distance + 1)) {
                        q[distance + 1].push_back(v);
                        cnt++;
                    }
                }
            }
            else {
                if (minimize(dis[v[0]][v[1]][v[2]], distance)) {
                    q[distance].push_back(v);
                    cnt++;
                }
            }
        }
    }

    // for(int i = 1; i<=w; ++i) {
    //     for(int j = 1; j<=h; ++j) cout << dp[l][r][i][j] << " ";
    //     cout << "\n";
    // }
    // cout << "\n";
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> w >> h;
    swap(w, h);
    if (n == 1){
        cout << 0 << "\n";
        return 0;
    }
    for(int i = 0; i<=w+1; ++i) 
    for(int j = 0; j<=h+1; ++j) grid[i][j] = obstacle;
    for(int i = 0; i<w; ++i){
        string s; cin >> s;
        for(int j = 0; j<h; ++j){
            if (s[j] == '.') grid[i+1][j+1]=none;
            else if (s[j] == 'x') grid[i+1][j+1] = obstacle;
            else if (s[j] == 'A') grid[i+1][j+1] = anti_clockwise;
            else if (s[j] == 'C') grid[i+1][j+1] = clockwise;
            else {
                grid[i+1][j+1]=none;
                pos[s[j] - '0' - 1] = {i + 1, j + 1};
            }
        }
    }

    memset(dp, 63, sizeof dp);

    for(int i = 0; i<n; ++i){
        dp[convert(i, i)][pos[i].first][pos[i].second] = 0;
    }

    for(int i = n-1; i>=0; --i)
    for(int j = i; j<n; ++j){
        dijkstra(i, j);
    }
    
    int ans = INF;
    for(int i = 1; i<=w; ++i) for(int j = 1; j<=w; ++j) 
        minimize(ans, dp[convert(0, n-1)][i][j]);

    if (ans == INF) ans = -1;
    cout << ans << "\n";


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57168 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57236 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 10 ms 57180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57168 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57236 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 10 ms 57180 KB Output is correct
6 Correct 10 ms 57240 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57288 KB Output is correct
9 Correct 10 ms 57180 KB Output is correct
10 Correct 9 ms 57180 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57168 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57236 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 10 ms 57180 KB Output is correct
6 Correct 10 ms 57240 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57288 KB Output is correct
9 Correct 10 ms 57180 KB Output is correct
10 Correct 9 ms 57180 KB Output is correct
11 Correct 145 ms 78672 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 70 ms 57520 KB Output is correct
14 Correct 293 ms 89880 KB Output is correct
15 Correct 100 ms 62588 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57168 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57236 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 10 ms 57180 KB Output is correct
6 Correct 10 ms 57240 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57288 KB Output is correct
9 Correct 10 ms 57180 KB Output is correct
10 Correct 9 ms 57180 KB Output is correct
11 Correct 145 ms 78672 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 70 ms 57520 KB Output is correct
14 Correct 293 ms 89880 KB Output is correct
15 Correct 100 ms 62588 KB Output is correct
16 Correct 162 ms 57356 KB Output is correct
17 Runtime error 826 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -