Submission #940504

#	Time	Username	Problem	Language	Result	Execution time	Memory
940504		stev2005	Robots (APIO13_robots)	C++17	0 / 100	1 ms	600 KiB

robots

#include<bits/stdc++.h>
using namespace std;
const int maxh = 16, maxw = 16;
const int maxv = maxh * maxw;

struct robot{
    int a, b;///a-lowest label, b-highest label
    int wh;///position 
    robot(){
        a = 0;
        b = 0;
        wh = -1;
    }
    robot(int _a, int _b, int _wh){
        a = _a;
        b = _b;
        wh = _wh;
    }
    bool operator<(const robot &other)const{
        if (a != other.a) return a < other.a;
        if (b != other.b) return b < other.b;
        return wh < other.wh;
    }
};

int n, w, h;
vector<int> v[maxv];
string net[maxh];
vector<robot> rs;
int dir[4][maxh][maxw];

void speed(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void read(){
    cin >> n >> w >> h;
    for (int i = 1; i <= h; ++i)
        cin >> net[i];
}

bool is_valid_cell_to_pass(int i, int j){
    if (i < 0 && h < i)
        return false;
    if (j < 0 && w < j)
        return false;
    if (net[i][j] == 'x')
        return false;
    return true;
}

int get_cell_num(int i, int j){
    return i * h + j + 1;
}

int get_d(int i, int j, int d){
    switch(net[i][j]){
        case '.': break;
        case '1': break;
        case '2': break;
        case '3': break;
        case '4': break;
        case '5': break;
        case '6': break;
        case '7': break;
        case '8': break;
        case '9': break;
        case 'A': --d;
                  if (d == -1) d = 3;
                  break;
        case 'C': ++d; d %= 4;
                  break;  
        default: assert(false);
    }
    return d;
}

pair<int, int> get_nextcell(int i, int j, int d){
    pair<int, int> ret;
    switch(d){
        case 0: ret.first = i - 1;
                ret.second = j;
                break;
        case 1: ret.first = i;
                ret.second = j + 1;
                break;
        case 2: ret.first = i + 1;
                ret.second = j;
                break;
        case 3: ret.first = i;
                ret.second = j - 1;
                break;
        default: assert(false);
    }
    return ret;
}

inline void decode_net(){
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            for (int k = 0; k < 4; ++k){
                if (dir[k][i][j]){
                    /*int cellnum = get_cell_num(i, j);
                    v[cellnum].push_back(dir[k][i][j]);*/
                    continue;
                }
                stack<pair<pair<int, int>, int> > cells;
                pair<int, int> cur_cell = {i, j};
                pair<int, int> next_cell;
                cells.push({cur_cell, k});
                int d;
                do{
                    cur_cell = cells.top().first;
                    d = get_d(cur_cell.first, cur_cell.second, cells.top().second);
                    next_cell = get_nextcell(cur_cell.first, cur_cell.second, d);
                    cells.push({next_cell, d});
                }while(!is_valid_cell_to_pass(next_cell.first, next_cell.second) &&
                       !dir[d][next_cell.first][next_cell.second]);

                pair<int, int> occur_cell;
                int occur_num;
                if (!is_valid_cell_to_pass(next_cell.first, next_cell.second)){
                    cells.pop();
                    occur_cell = cells.top().first;
                    occur_num = get_cell_num(occur_cell.first, occur_cell.second);
                }
                else{
                    occur_cell = cells.top().first;
                    occur_num = dir[cells.top().second][occur_cell.first][occur_cell.second];
                    cells.pop();
                }
                while (!cells.empty()){
                    cur_cell = cells.top().first;
                    d = cells.top().second;
                    cells.pop();
                    dir[d][cur_cell.first][cur_cell.second] = occur_num;
                    int cur_num = get_cell_num(cur_cell.first, cur_cell.second);
                    v[cur_num].push_back(cur_num);
                }
            }
}

void inline find_start_positions(){
    rs.resize(n);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if ('1' <= net[i][j] && net[i][j] <= '9'){
                int numr = net[i][j] - '0';
                int numcell = get_cell_num(i, j);
                rs[numr].a = numr;
                rs[numr].b = numr;
                rs[numr].wh = numcell;
            }
}

/*int availrobots(int exa, int exb, int wh){
    for (int i = 0; i < (int)rs.size(); ++i){
        auto r = rs[i];
        if (r.a != exa && r.b != exb && r.wh == wh)
            return i;
    }
    return -1;
}

void inline BFS(){
    find_start_positions();
    set<pair<int, int> > nonexistence;
    map<robot, int> rpushes;
    queue<robot> q;
    for (auto r: rs){
        q.push(r);
        rpushes[r] = 0;
    }
    while (!q.empty() && (int)rs.size() > 1){
        robot cur = q.front();
        q.pop();
        if (nonexistence.find({cur.a, cur.b}) != nonexistence.end())
            continue;
        int idxavailr = availrobots(cur.a, cur.b, cur.wh);
        if (idxavailr != -1){
            nonexistence.
        }
        for (auto nb: v[cur.wh])
    }
}*/

int used[2][maxv];

void BFS_two_robots(){
    find_start_positions();
    queue<robot> q;
    for (int i = 0; i < 2; ++i){
        rs[i].a--;
        rs[i].b--;
        auto r = rs[i];
        used[i ^ 1][r.wh] = 1;
        q.push(r);
    }
    while (!q.empty()){
        robot cur = q.front();
        q.pop();
        for (auto nb: v[cur.wh]){
            used[cur.a][nb] = used[cur.a][cur.wh] + 1;
            if (used[cur.a ^1][nb]){
                cout << used[cur.a][nb] + used[cur.a ^ 1][nb] - 2;
                return;
            }
            q.push(robot(cur.a, cur.b, nb));
        }
    }
    
}

int main(){
    read();
    decode_net();
    BFS_two_robots();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40